QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115391#6629. Travelling TraderMr_Eight#2 109ms65872kbC++143.4kb2023-06-26 08:41:462024-05-31 14:12:50

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 14:12:50]
  • 评测
  • 测评结果:2
  • 用时:109ms
  • 内存:65872kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 08:41:46]
  • 提交

answer

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#define int long long
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
	template<class T>
	inline void read(T &x) {
		x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		if(fu)x=-x;
	}
	inline int read() {
		int x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		return fu?-x:x;
	}
	template<class T,class... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
	char _n_u_m_[40];
	template<class T>
	inline void write(T x) {
		if(x==0){
			putchar('0');
			return;
		}
		T tmp = x > 0 ? x : -x ;
		if( x < 0 ) putchar('-') ;
		register int cnt = 0 ;
		while( tmp > 0 ) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
			tmp /= 10 ;
		}
		while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template<class T>
	inline void write(T x ,char ch) {
		write(x);
		putchar(ch);
	}
}
using namespace fastIO;
int n,k,f[200002],h[200002],p[200002],v[200002],fa[200002];
bool vis[200002];
pii mmax[200002],sec[200002];
pair<int,pii >ans;
vector<pii >g[200002];
vector<int>q;
inline void dfs(int pos,int lst){
	fa[pos]=lst;
	mmax[pos]=sec[pos]={v[pos],pos};
	for(pii i:g[pos])if(i.first!=lst){
		dfs(i.first,pos);
		mmax[i.first].first+=i.second+v[pos];
		if(mmax[pos]<mmax[i.first])sec[pos]=mmax[pos],mmax[pos]=mmax[i.first];
		else sec[pos]=max(sec[pos],mmax[i.first]);
	}
}
inline void D(int pos,int res){
	q.push_back(pos);vis[pos]=true;
	if(res!=1)for(auto i:g[pos])if(!vis[i.first])D(i.first,res-1);
}
inline void solve(int pos){
	if(pos!=1)solve(fa[pos]);
	D(pos,k);
}
signed main() {
	cin>>n>>k;
	F(i,2,n){
		int u=read(),v=read();
		g[u].push_back({v,0});
		g[v].push_back({u,0});
	}
	F(i,1,n)read(p[i]),f[i]=h[i]=p[i];
	F(pos,1,n)for(pii i:g[pos])f[pos]+=p[i.first];
	F(pos,1,n)for(pii i:g[pos])h[pos]+=f[i.first]-p[pos];
	if(k==1){
		F(i,1,n)v[i]=p[i];
	}else if(k==2){
		F(i,1,n)v[i]=f[i];
		F(pos,1,n)for(pii &i:g[pos])i.second=-p[pos]-p[i.first];
	}else if(k==3){
		F(i,1,n)v[i]=h[i];
		F(pos,1,n)for(pii &i:g[pos])i.second=p[pos]+p[i.first]-f[pos]-f[i.first];
	}
//	F(i,1,n)cerr<<v[i]<<" ";cerr<<endl;
	dfs(1,0);
	cout<<mmax[1].first<<endl;
	for(int i=mmax[1].second;i;i=fa[i])vis[i]=true;
	solve(mmax[1].second);
	write(q.size(),'\n');
	for(auto i:q)write(i,' ');
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 0ms
memory: 20372kb

input:

2 1
1 2
255959470 961356354

output:

1217315824
2
1 2 

result:

ok correct!

Test #2:

score: 2
Accepted
time: 0ms
memory: 20508kb

input:

1000 1
730 89
762 280
923 523
740 22
679 350
448 769
102 712
154 965
219 32
238 289
484 502
183 311
999 682
806 450
275 101
131 197
749 720
131 937
960 202
503 320
95 262
595 133
809 560
659 451
843 218
258 842
564 316
729 727
413 237
606 531
469 258
612 8
707 539
359 680
957 639
381 708
104 490
234...

output:

95535
17
1 173 449 472 396 545 668 270 981 489 852 836 763 6 218 843 758 

result:

ok correct!

Test #3:

score: 2
Accepted
time: 55ms
memory: 32928kb

input:

200000 1
111811 133538
179217 151840
171974 117009
187613 169656
64662 13136
132434 89348
52802 175565
194821 191312
196047 99457
40339 152969
29669 180026
147677 57771
119598 58048
80707 146623
72232 101624
48109 11800
71536 69
31573 129
24409 17263
1033 148614
66977 149926
138624 87653
141889 1178...

output:

221
35
1 145832 90178 52464 3517 55709 39776 67451 59386 143855 102872 38865 13093 177086 7366 190908 160039 69864 196809 13257 612 171083 182883 14221 93359 52156 27994 103745 151704 138607 5346 14735 29598 89600 128747 

result:

ok correct!

Test #4:

score: 2
Accepted
time: 69ms
memory: 32844kb

input:

200000 1
102636 78442
179388 84484
161437 35179
102313 154299
62439 71542
176361 125315
174129 186376
180886 54947
154823 114239
174647 112385
136495 187134
157035 96260
101101 192444
58209 23947
55494 191600
168007 162648
140149 73180
130665 180633
129328 67380
90262 134914
185905 104220
111321 154...

output:

21795891322
36
1 13557 199188 104317 71891 69787 1221 63258 191536 179446 83510 187880 124824 43888 83237 194602 59080 196038 195977 18490 43421 110298 60011 137785 140692 48345 68279 128780 198550 29394 56331 112092 192199 177180 16418 142142 

result:

ok correct!

Test #5:

score: 2
Accepted
time: 70ms
memory: 33124kb

input:

200000 1
682 75953
92444 160568
113369 93705
154622 193304
149619 128186
104784 48913
131684 161196
25886 151867
89191 19511
99233 137377
104650 120096
64347 93526
111350 71598
7568 120116
123497 76821
25436 190715
99884 33654
109438 69462
165464 2475
163215 34551
33926 85078
101208 193355
50705 828...

output:

99327575017
197
1 178606 82034 53029 10508 21404 203 109187 121716 142023 3901 36728 9916 192913 18250 170199 113960 179753 163922 179588 31797 31645 183321 83207 13973 128176 38001 160968 9055 62809 168173 43933 187373 123795 114656 2192 193151 25062 141855 133596 155793 64049 57320 93903 33957 139...

result:

ok correct!

Test #6:

score: 2
Accepted
time: 46ms
memory: 33212kb

input:

200000 1
91999 92900
195726 58991
132067 99937
168188 152017
188495 19779
105961 45241
53406 75757
85118 170259
46250 47585
132248 8609
195110 32777
164307 95643
133411 739
170952 145623
19297 14414
171045 97619
74663 193421
139543 189434
36319 56453
77520 91164
91469 30021
128798 62259
183807 15271...

output:

9098893435
13
1 164355 56677 150505 174723 115829 88068 105453 199874 190131 165416 182628 114943 

result:

ok correct!

Test #7:

score: 2
Accepted
time: 44ms
memory: 31828kb

input:

200000 1
189797 1
1 148138
1 95067
141831 1
168151 1
1 25692
95612 1
1 135979
1 141581
119622 1
1 131946
86508 1
98799 1
1 189104
1 117526
46338 1
1 166375
1 28026
165221 1
54204 1
1 98743
1 181414
1 34313
1 71302
1 161200
1 146339
1 47014
1 137258
1 57857
1 196493
1 99105
54487 1
104725 1
1 45203
1...

output:

1175349557
2
1 153544 

result:

ok correct!

Test #8:

score: 2
Accepted
time: 52ms
memory: 31884kb

input:

199999 1
56367 178046
1 156890
170478 1
111308 177326
1 188427
1 90169
126610 1
161930 167698
96500 126424
118330 158517
186608 1
95505 107863
1 142887
72279 27494
1 114700
118535 1
68584 63156
97555 19966
39239 1
128030 1
1 86200
66974 1
34616 47100
173578 1
1 117279
89769 43412
1 89670
103573 1
13...

output:

2999144210
3
1 52552 129910 

result:

ok correct!

Test #9:

score: 2
Accepted
time: 109ms
memory: 65872kb

input:

200000 1
95601 67789
174512 65854
198542 123861
153390 92355
141969 168754
177054 101194
25665 15524
131869 168080
171051 30732
97293 119758
103002 59019
141990 124310
161550 116618
2585 170410
132999 38200
99202 98733
73949 155033
144918 64086
1594 34916
37138 165382
13452 170885
136973 62178
15250...

output:

200000000000000
200000
1 47213 179780 132180 145558 41335 179095 156350 24912 104386 94658 54370 97034 108043 73905 141018 157563 199841 176455 147422 87545 190562 135095 24903 62484 36389 156106 45144 120321 4911 173474 102976 13602 68252 7332 141515 59337 182112 124040 38089 15458 161370 41901 144...

result:

ok correct!

Test #10:

score: 2
Accepted
time: 94ms
memory: 50604kb

input:

200000 1
122636 169264
76896 89915
72116 125306
186356 74852
84394 177419
21725 144848
106395 111991
189102 195804
6151 170169
185460 146764
6304 149801
147880 99539
6202 175326
104277 26515
39402 33436
116555 185545
44341 92305
197925 125286
28215 102176
182103 160554
105237 169007
105618 75618
190...

output:

49951940813408
100001
1 88700 18534 14218 21693 84470 150823 121376 192964 139616 11067 93019 188349 55336 13628 87630 31553 28945 29827 140175 179655 10038 38915 99968 89953 72978 102045 45280 176852 171879 100086 93399 183932 84482 111738 112608 136016 101850 19371 96135 54333 95939 2865 140685 13...

result:

ok correct!

Test #11:

score: 2
Accepted
time: 22ms
memory: 33460kb

input:

200000 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54...

output:

13954593167
18
1 2 5 10 20 40 80 161 323 647 1295 2590 5181 10363 20727 41454 82908 165817 

result:

ok correct!

Subtask #2:

score: 0
Wrong Answer

Test #12:

score: 7
Accepted
time: 0ms
memory: 19768kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2 

result:

ok correct!

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 20320kb

input:

10 2
6 4
3 7
5 10
6 10
8 2
3 9
3 5
4 2
1 4
2 4 2 5 5 4 2 3 4 2

output:

30
9
1 4 2 6 10 5 3 7 9 

result:

wrong answer your profit is 30 but jury's plan is 33, your plan is not optimal!

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #83:

score: 4
Accepted
time: 0ms
memory: 20364kb

input:

2000 3
1359 90
1703 163
158 188
360 1501
195 664
1414 215
1546 1756
536 1096
1726 1223
1150 104
1757 703
1982 282
1023 998
1180 419
576 1759
1496 1993
44 670
1703 952
855 849
1998 1399
1280 980
1533 1090
1270 678
1680 387
469 1734
1799 263
473 588
303 226
5 295
1489 1471
1094 1667
1912 210
1368 1360...

output:

1008611451196
2000
1 379 1954 1539 531 605 961 1091 1613 1300 540 377 1565 1823 1237 454 1101 99 864 359 1866 1840 1369 1617 562 867 1831 243 710 1040 901 1256 709 88 916 1341 1158 1526 1238 1291 129 745 260 1967 773 1919 816 523 674 1788 832 890 1626 297 452 1961 1903 1349 1808 1428 1337 739 560 16...

result:

ok correct!

Test #84:

score: 4
Accepted
time: 4ms
memory: 19832kb

input:

2000 3
1727 567
1783 1850
205 985
323 1094
1153 821
1756 117
377 1928
1026 1303
1343 1814
268 745
242 948
1140 1218
7 1675
101 1798
1403 1752
1184 671
87 248
1953 30
1580 1441
507 1438
525 419
901 421
1585 1405
1575 883
1952 1930
1988 1325
615 722
994 1202
178 474
1978 1500
899 481
216 409
999 1817
...

output:

1012330476243
2000
1 598 1789 369 488 525 419 422 269 694 1079 202 1379 1545 1454 1724 88 701 246 1123 1522 1364 1696 1158 1918 1832 1589 131 872 345 1057 1532 1725 1634 761 67 1174 650 1807 719 693 554 718 61 841 175 234 1935 220 1784 917 105 997 92 1530 1315 257 1369 802 1071 1257 993 1275 1046 31...

result:

ok correct!

Test #85:

score: 0
Wrong Answer
time: 0ms
memory: 18960kb

input:

2000 3
1213 130
101 508
72 1199
1550 1096
1099 861
1515 627
1299 1672
1338 105
1444 1019
15 1560
1949 971
52 1312
30 529
186 1687
1917 484
1971 349
537 1223
1955 1377
300 1060
1786 1811
1960 90
1959 1353
1831 1548
303 511
1073 1197
863 1527
1379 994
31 9
1247 1707
1395 1532
29 1544
119 296
1919 1554...

output:

499518764997
1004
1 1986 1487 1365 1821 1255 513 668 1557 1491 574 751 60 1292 640 1261 1450 1246 1710 1896 706 954 295 1377 242 435 93 1809 1127 181 863 384 1503 563 1169 1153 1475 1069 1303 1310 1483 262 1181 832 57 854 358 674 63 625 1709 1357 572 150 1372 1199 1152 1855 372 1374 1368 434 578 130...

result:

wrong answer your profit is 499518764997 but jury's plan is 1001405462082, your plan is not optimal!

Subtask #6:

score: 0
Skipped

Dependency #5:

0%