QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624530#6102. Query on a TreeDreamAwakingRE 91ms14372kbC++142.1kb2024-10-09 16:02:212024-10-09 16:02:22

Judging History

This is the latest submission verdict.

  • [2024-10-09 16:02:22]
  • Judged
  • Verdict: RE
  • Time: 91ms
  • Memory: 14372kb
  • [2024-10-09 16:02:21]
  • Submitted

answer

#include <bits/stdc++.h>
#define db(x) cerr<<#x<<" "<<(x)<<"\n" 
#define db1(x) cerr<<#x<<" "<<(x)<<" "
#define rep(i,a,b) for(int i=a;i<=b;i++) 
#define ll long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using pii = pair<int,int>;
const int N = 2e5+10;
int n,m,q,k,f,fa[N],siz[N],par[N],tmp[N];
int vis[N];
ll ans;
vector<int>  v[N];
void dfs(int x,int f){
	par[x] =f;
	for(auto y:v[x]){
		if(y==f)continue;
		dfs(y,x);
	}
}
int find(int x){
	return x==fa[x]?x:fa[x] =find(fa[x]);
}
ll f1(int x){
	return 1ll*x*(x-1)/2;
}
void Union(int x,int y){
	x = find(x),y = find(y);
	if(x==y)return ;
	fa[x] = y;
	// if(siz[x]>siz[y])swap(x,y);
	// fa[x] = y;
	// ans-=f1(siz[x])+f1(siz[y]);
	// siz[y]+=siz[x];
	// ans+=f1(siz[y]);
}

void solve()
{
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,-1);
	cin>>q;
	for(int i=1;i<=n;i++)fa[i] =i,siz[i] =1;
	for(int t =1;t<=q;t++){
		ans =0;
		cin>>k;
		for(int i=1;i<=k;i++){
			int x;cin>>x;tmp[i] =x;vis[x] =1;
		}
		for(int i=1;i<=k;i++){
			int x = tmp[i],y = par[x];
			if(y==-1||!vis[y])continue;
			Union(x,y);
		}
		for(int i=1;i<=k;i++){
			vis[tmp[i]] =0;
		}
		for(int i=1;i<=k;i++){
			vis[find(tmp[i])]++;
		}
		for(int i=1;i<=k;i++){
			int x =tmp[i];
			if(find(x)==x)ans+=f1(vis[x]);
		}
		cout<<ans<<"\n";

		//cout<<"ans = "<<ans<<"\n";
		// map<int,int> mp;
		// for(int i=1;i<=k;i++){
			// mp[find(tmp[i])]++;
		// }
	// //	ans =0;
	// //	cout<<" t = "<<t<<"\n";
		// for(auto [x,num]:mp){
			// //ans+=num*(num-1)/2;
		// //	cout<<"x = "<<x<<" num ="<<num<<"\n";
		// }
		for(int i=1;i<=k;i++){
			int x = tmp[i];
			vis[tmp[i]] =0;
			fa[tmp[i]] = tmp[i],siz[tmp[i]] = 1;
		}
	//	for(int i=1;i<=n;i++)db1(fa[i]);db(1);
	//	for(int i=1;i<=n;i++)db1(siz[i]);db(1);
		// for(int i=1;i<=n;i++){
			// if(fa[i]!=i)cout<<"NP\n";
		// }
	//	cout<<ans<<"\n";
	}
	
	
	return ;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	while(_--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11668kb

input:

7
1 2
1 3
1 5
2 7
4 6
4 7
6
1 1
2 1 2
4 1 2 3 4
5 1 2 4 6 7
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7

output:

0
1
3
10
7
21

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 11048kb

input:

3
1 3
2 1
1000
3 1 3 2
3 2 3 1
3 1 3 2
3 3 2 1
2 2 1
2 2 1
2 2 3
3 3 2 1
2 1 2
2 1 2
2 3 1
3 3 2 1
3 3 2 1
3 3 2 1
2 1 2
2 3 2
2 2 3
2 3 1
2 1 2
2 2 1
3 3 1 2
3 1 2 3
3 2 3 1
2 1 3
3 2 3 1
3 1 3 2
2 2 1
2 2 3
2 2 3
2 2 3
2 1 3
2 1 3
2 3 2
2 1 3
3 1 2 3
3 2 1 3
2 3 2
2 1 3
3 2 1 3
2 2 1
2 2 1
3 3 2 1...

output:

3
3
3
3
1
1
0
3
1
1
1
3
3
3
1
0
0
1
1
1
3
3
3
1
3
3
1
0
0
0
1
1
0
1
3
3
0
1
3
1
1
3
1
1
3
3
1
0
3
3
3
1
1
3
3
1
3
1
3
0
1
1
3
0
3
1
3
3
1
3
1
3
1
1
0
0
0
0
1
0
1
3
3
0
3
1
3
3
1
3
3
3
1
1
1
3
3
1
3
0
1
1
3
3
0
1
3
1
1
1
3
0
3
0
3
3
3
3
3
0
3
3
3
0
3
3
3
3
3
1
1
0
3
1
1
1
1
1
3
1
3
0
1
0
0
1
3
3
3
1
...

result:

ok 1000 numbers

Test #3:

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

input:

3
1 3
2 3
10000
3 2 3 1
3 1 2 3
2 2 1
3 3 2 1
3 2 3 1
3 2 3 1
3 2 3 1
3 2 1 3
2 3 1
2 3 1
3 1 2 3
2 2 3
2 2 1
2 2 3
2 2 3
2 2 3
3 3 1 2
2 1 3
2 3 1
3 3 2 1
3 1 2 3
2 1 3
2 2 1
2 2 3
3 3 2 1
2 2 3
3 2 3 1
3 1 3 2
3 2 3 1
2 2 1
2 2 1
3 3 2 1
2 1 2
3 3 2 1
2 1 2
3 3 1 2
3 3 2 1
2 3 1
3 3 2 1
3 2 3 1
2 ...

output:

3
3
0
3
3
3
3
3
1
1
3
1
0
1
1
1
3
1
1
3
3
1
0
1
3
1
3
3
3
0
0
3
0
3
0
3
3
1
3
3
1
0
0
3
1
3
3
3
3
1
1
3
1
0
3
0
1
1
0
3
1
3
3
1
3
0
0
0
3
3
1
1
1
0
3
3
3
1
0
1
3
0
3
1
3
0
3
3
3
3
3
3
3
1
1
3
3
0
1
3
3
1
3
0
1
1
3
3
3
3
3
1
1
0
3
3
3
1
1
0
0
0
1
0
3
1
1
3
1
0
3
1
3
0
3
3
3
0
3
3
0
3
1
3
3
3
3
3
3
1
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 19ms
memory: 10844kb

input:

3
3 1
2 3
100000
2 3 1
2 2 3
3 1 3 2
3 1 2 3
2 2 3
2 1 2
2 2 1
3 2 3 1
3 2 3 1
3 2 1 3
3 1 3 2
3 1 3 2
3 2 1 3
2 2 1
3 1 2 3
2 3 2
3 2 1 3
3 1 3 2
2 3 1
3 3 2 1
2 1 2
2 2 1
3 2 1 3
2 2 1
3 2 1 3
2 1 3
3 1 3 2
2 2 3
2 3 1
2 2 1
2 1 3
3 1 3 2
3 1 2 3
3 3 1 2
2 3 2
3 2 3 1
2 3 1
3 1 2 3
2 3 1
2 2 1
3 1...

output:

1
1
3
3
1
0
0
3
3
3
3
3
3
0
3
1
3
3
1
3
0
0
3
0
3
1
3
1
1
0
1
3
3
3
1
3
1
3
1
0
3
1
1
3
0
0
1
3
1
3
0
1
1
0
3
1
0
3
3
1
1
3
3
3
0
3
3
1
1
3
1
3
3
3
3
1
3
1
3
3
3
0
0
0
1
0
0
3
1
1
3
0
1
1
3
1
1
3
0
3
3
3
1
3
1
3
3
1
3
1
3
1
3
1
3
1
1
3
3
3
0
3
3
1
3
3
1
1
3
3
1
3
3
1
0
3
3
3
1
0
3
1
1
0
3
3
3
1
3
3
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 11920kb

input:

13
4 7
8 2
5 11
5 9
3 11
1 2
11 10
6 7
7 1
6 12
4 11
13 12
27
13 11 5 8 10 13 2 9 4 6 12 1 3 7
10 9 5 4 3 11 2 13 8 7 10
8 1 12 13 9 6 5 10 11
11 2 8 13 10 7 9 3 4 1 11 12
9 8 3 9 13 11 6 1 10 4
8 3 4 8 5 10 6 7 13
10 11 12 5 4 1 7 3 2 10 9
10 10 4 11 2 5 13 6 7 8 3
9 6 1 11 8 2 5 9 13 12
10 4 8 9 6...

output:

78
22
9
29
6
3
36
22
9
45
36
5
7
16
16
46
4
8
78
66
78
45
46
45
13
11
11

result:

ok 27 numbers

Test #6:

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

input:

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

output:

130
634
425
95
991
1081
265
98
562
574
204
329
222
990
400
1225
1225
43
254
777
195
1081
255
1035
89
918
1225
177
531
86
841
238
110
1036
1225
334
867
67
451
126
106
71
156
118
443
104
96
66
218
29

result:

ok 50 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 11700kb

input:

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

output:

129
114
408
296
56
706
239
242
1225
279
269
990
84
124
411
185
60
129
132
128
481
51
155
63
192
116
162
742
136
992
659
38
191
73
204
709
225
134
862
490
787
90
146
407
1225
259
946
359
93
276

result:

ok 50 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 11024kb

input:

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

output:

532
309
1225
490
1176
1225
89
45
406
903
168
151
332
112
1035
122
223
861
1081
1035
324
290
946
251
190
990
1225
153
238
1225
1128
109
199
302
148
240
1225
160
467
867
253
504
129
82
946
359
147
82
905
381

result:

ok 50 numbers

Test #9:

score: 0
Accepted
time: 54ms
memory: 11128kb

input:

2125
1692 784
76 63
37 1633
736 46
1644 1621
893 1413
1100 671
318 150
1207 30
777 1693
569 2061
2090 1731
487 1766
1749 1094
1128 1860
564 486
405 1842
848 977
1357 832
571 1378
1638 1064
423 132
251 1118
367 965
328 351
102 433
2088 763
353 962
857 2046
944 105
1337 683
123 372
1306 1409
424 2026
...

output:

1186
3088
3
45801
24
6
1
2
16666
50392
8028
24
248782
97903
115
26304
50656
34
11398
977
1414
1654
113418
1313623
45
83432
650584
78767
6633
1405
249
35778
7123
248
227
2
52228
14433
2024749
6765
12634
1353
2158
14498
252
14064
365
914
190
5757
17
57
10345
12731
2424
2773
1280269
238371
42821
6337
3...

result:

ok 687 numbers

Test #10:

score: 0
Accepted
time: 63ms
memory: 10964kb

input:

2500
1397 89
1576 1217
892 95
783 1361
1399 651
696 319
1067 622
149 318
275 748
1950 251
2085 1593
714 930
2462 2494
1352 1531
2187 866
1238 789
480 2373
1658 1906
2013 853
1279 2212
1584 2284
1345 1578
33 478
1786 485
2182 1157
2438 63
695 1124
792 628
375 2188
134 2064
1909 1963
1562 566
1932 220...

output:

271791
10323
4881
0
0
292793
0
0
14323
0
0
297
0
0
0
0
0
0
1
0
5890
0
17889
0
0
0
3657
16
348
338
0
0
0
0
0
0
0
0
0
0
0
54123
0
0
1
0
49
0
0
0
0
5681
223
0
0
0
11
309
0
0
0
0
103699
0
0
0
0
301408
1
0
0
0
0
0
0
0
0
0
51966
0
0
0
0
0
21334
0
4858
3684
0
18
1304
0
0
0
1071
0
0
1
0
329
0
0
0
0
0
0
0
69...

result:

ok 2500 numbers

Test #11:

score: 0
Accepted
time: 63ms
memory: 11708kb

input:

2500
2321 1434
2130 898
145 1168
470 145
555 37
1136 267
1157 1851
472 735
701 806
2469 1992
834 1871
723 1801
1523 202
369 1187
2307 328
2156 1263
876 806
1062 2314
1947 927
1017 427
2081 1206
2329 1236
1530 1562
1098 2025
300 1520
551 1819
1084 549
1392 1374
1558 1513
181 2368
612 1569
897 344
146...

output:

0
0
0
0
0
2047
0
0
17016
27023
0
1046
7951
0
46
0
7805
38643
0
1064
0
0
6027
0
0
0
0
0
57
25321
0
0
0
0
0
0
0
0
0
1354
298011
0
0
0
317649
92
230
30101
0
0
0
0
4079
0
0
198
0
0
213837
0
0
0
0
0
0
0
0
705
485
0
0
0
0
0
0
2575
0
25624
4228
0
0
0
0
0
0
0
104
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7715
103881
...

result:

ok 2500 numbers

Test #12:

score: 0
Accepted
time: 63ms
memory: 11408kb

input:

2500
746 278
2080 2068
3 2444
1646 1837
2210 1719
1779 614
2056 1592
2487 1152
116 261
487 2449
2286 457
732 1184
2072 614
2294 1252
1620 198
1178 2137
667 250
875 222
1473 2490
958 537
682 1821
1418 690
2422 350
205 1269
1522 2283
1369 2359
1073 2073
2392 1109
649 634
1036 173
1815 2390
436 122
119...

output:

0
0
0
1
0
5
0
0
0
0
1082
0
0
0
0
0
1
0
0
0
0
372
0
0
1571
0
0
22336
0
650
35049
0
6154
56
0
0
5402
0
0
10493
0
0
15
0
0
455
563527
0
9697
0
261
0
0
0
0
0
16772
0
0
0
17
938
226069
33878
0
0
0
253
0
1026
0
0
0
0
0
0
0
0
0
1843
0
0
0
0
466
37564
0
0
66
0
0
0
1
0
69
332
471
0
2215
0
0
0
0
27160
0
0
210...

result:

ok 2500 numbers

Test #13:

score: 0
Accepted
time: 59ms
memory: 12260kb

input:

2500
1874 1418
133 1750
1756 209
1129 825
1570 902
2015 358
2350 526
310 1569
338 319
1209 1690
1035 939
1346 363
1133 823
1515 305
1740 877
405 2408
254 978
484 2322
1406 269
492 444
975 2231
2199 145
611 1433
2221 309
2140 145
1779 1615
1667 893
84 843
2239 1447
1687 1489
1531 1995
2067 708
729 28...

output:

591
0
0
0
118
0
0
0
0
0
139031
0
20316
0
397
0
0
0
0
54
0
0
0
0
0
18749
755186
0
0
0
502
0
0
33
515
0
0
0
645343
0
3389
1536
0
0
0
0
0
0
0
0
55
0
0
0
0
0
0
24
0
0
18781
0
0
0
3605
0
0
4905
1
0
0
1057
0
0
0
4403
0
0
13858
0
0
1183
0
180
0
0
3463
36165
1865
0
0
73120
0
0
0
31150
0
0
0
0
0
0
0
0
0
0
58...

result:

ok 2500 numbers

Test #14:

score: 0
Accepted
time: 59ms
memory: 12120kb

input:

2500
298 263
2379 1227
1818 1486
612 2313
929 84
159 2398
2440 267
2325 1986
561 2273
1727 1134
1475 1012
1355 2246
194 1839
533 166
1052 747
1323 986
853 2115
1989 26
1136 344
230 1363
2279 1153
684 2303
2108 221
2136 1849
54 908
905 667
1452 522
480 781
1126 568
1938 1793
438 316
2414 486
464 1649...

output:

0
5427
0
0
0
0
0
0
0
0
0
0
0
4372
0
2003
0
0
485
0
0
0
0
0
0
0
212
0
0
0
0
0
0
0
0
597
0
0
0
3674
152
0
0
1302
1827
1
0
0
0
0
0
0
5561
0
0
0
0
0
0
15125
0
0
0
0
0
0
0
5
0
0
1203
0
1250
14230
0
0
0
0
0
0
0
0
0
1307
1744
8639
0
0
203690
0
0
0
0
66468
0
101386
147201
6402
0
0
0
518
0
0
0
0
0
0
0
0
1142...

result:

ok 2500 numbers

Test #15:

score: 0
Accepted
time: 91ms
memory: 14372kb

input:

98246
3650 41804
33441 91212
31858 45777
26280 1021
42752 11638
69613 11500
24634 34071
92610 60294
8935 87882
86958 14022
51707 53093
90392 66077
9263 41911
41042 5636
26146 40921
72138 89357
10979 5882
80910 93086
75618 66667
94037 20575
83310 29226
82200 75277
22984 72723
14257 19092
74647 97034
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 9843 numbers

Test #16:

score: -100
Runtime Error

input:

250000
214553 54714
71256 226500
127178 173505
85122 145888
186314 141085
76547 28443
149456 30947
12037 20860
120859 145004
123686 189726
115672 191621
176791 242640
204589 240143
172080 55269
49042 25311
163578 145461
226899 91039
47491 75338
155567 1692
32558 240020
185020 134550
154352 61766
173...

output:


result: