UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203305#3557. 平衡树wosile1001802ms28612kbC++111.3kb2024-02-22 10:06:042024-02-22 13:05:12

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
int n,Q;
vector<int>T[200005];
int U[200005],V[200005];
int tot=0;
int dfn[200005],dfr[200005];
void dfs(int x,int fa){
	dfn[x]=dfr[x]=++tot;
	for(int v:T[x])if(v!=fa){
		dfs(v,x);
		dfr[x]=dfr[v];
	}
}
int p[200005];
int c[200005];
inline int lowbit(int x){
	return x&(-x);
}
inline void add(int x,int val){
	// return;
	for(;x<=n;x+=lowbit(x))c[x]+=val;
}
inline int query(int x){
	int sum=0;
	for(;x;x-=lowbit(x))sum+=c[x];
	return sum;
}
int main(){
	scanf("%d%d",&n,&Q);
	for(int i=1;i<n;i++){
		scanf("%d%d",&U[i],&V[i]);
		T[U[i]].push_back(V[i]);
		T[V[i]].push_back(U[i]);
	}
	dfs(1,0);
	for(int i=1;i<n;i++)if(dfn[U[i]]>dfn[V[i]])swap(U[i],V[i]);
	while(Q--){
		int len;
		scanf("%d",&len);
		for(int i=1;i<=len;i++){
			scanf("%d",&p[i]);
			p[i]=V[p[i]];
		}
		for(int i=1;i<=len;i++)assert(dfn[p[i]]>0);
		for(int i=1;i<=len;i++)add(dfn[p[i]],1);
		int cnt=0;
		for(int i=1;i<=len;i++){
			int d=query(dfr[p[i]])-query(dfn[p[i]]-1);
			if(d==1)++cnt;
			if(d==len)++cnt;
		}
		int S;
		scanf("%d",&S);
		printf("%d\n",S-S/cnt*2);
		for(int i=1;i<=len;i++)add(dfn[p[i]],-1);
	}
	return 0;
}
// quod erat demonstrandum

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 5944kb

input:

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

output:

0
1

result:

ok 2 lines

Test #2:

score: 5
Accepted
time: 0ms
memory: 5948kb

input:

5 2
3 2
4 2
2 1
1 5
4 1 2 3 4 8
1 3 7

output:

4
1

result:

ok 2 lines

Test #3:

score: 5
Accepted
time: 3ms
memory: 6048kb

input:

2000 123
5 1633
10 46
11 1976
13 510
16 901
17 837
18 1845
19 745
25 1905
26 258
29 836
30 1198
31 2...

output:

2518
2972
5118
3616
4311
622
1
1
30
7414
1481
3969
1
4227
4190
2377
1272
1566
0
7355
5564
4181
1730
...

result:

ok 123 lines

Test #4:

score: 5
Accepted
time: 0ms
memory: 6040kb

input:

2000 154
3 1439
4 1463
8 657
12 449
13 1287
18 1067
24 1928
30 1909
31 172
33 370
36 104
37 1224
38 ...

output:

5420
5537
2309
5771
503
3077
1049
2518
1532
1202
1091
0
5173
7540
3174
3042
1067
3737
1443
5194
7374...

result:

ok 154 lines

Test #5:

score: 5
Accepted
time: 2ms
memory: 6048kb

input:

2000 149
1 1989
4 1751
5 1067
6 29
13 1388
14 930
15 473
19 1640
21 1425
28 70
29 1970
30 149
31 722...

output:

5084
433
7962
5703
0
214
0
1
7541
3121
91
1540
5101
32
0
1
1674
1456
3100
173
4953
2286
2019
5640
39...

result:

ok 149 lines

Test #6:

score: 5
Accepted
time: 2ms
memory: 6048kb

input:

2000 76
2 666
7 1415
8 468
9 375
13 1051
15 433
17 567
20 583
29 1255
30 651
31 475
34 1528
38 1249
...

output:

2584
2945
3540
819
5317
1890
7019
0
1596
919
6476
8336
5479
1843
0
856
7840
6429
3746
4726
0
2527
16...

result:

ok 76 lines

Test #7:

score: 5
Accepted
time: 83ms
memory: 28608kb

input:

200000 817
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1...

output:

1
1
0
1
1
1
0
0
1
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
...

result:

ok 817 lines

Test #8:

score: 5
Accepted
time: 80ms
memory: 28612kb

input:

200000 761
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1...

output:

1
1
1
0
1
1
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
1
0
0
0
1
0
...

result:

ok 761 lines

Test #9:

score: 5
Accepted
time: 153ms
memory: 16228kb

input:

200000 80031
2 56605
5 189458
10 52573
16 40609
20 147707
21 51606
25 85354
26 80273
28 146532
30 30...

output:

1
1
84592587
282777332
17448421
224692442
200184146
0
0
0
0
1
142630100
0
279438899
1
0
196329433
25...

result:

ok 80031 lines

Test #10:

score: 5
Accepted
time: 169ms
memory: 16196kb

input:

200000 80110
5 94780
7 25504
8 121345
10 55001
11 80845
15 75079
19 110524
20 24218
21 106900
33 474...

output:

125396798
287042965
1
1
0
266980734
227570895
276708838
235412257
193522402
290542021
92010025
1
154...

result:

ok 80110 lines

Test #11:

score: 5
Accepted
time: 147ms
memory: 16208kb

input:

200000 79935
2 73053
3 62426
5 10346
6 57113
9 161123
11 99199
13 33136
17 155443
18 39834
19 164439...

output:

209963314
168206964
83579270
7448413
0
0
2388804
66721195
144755864
166639227
5493227
0
280850279
18...

result:

ok 79935 lines

Test #12:

score: 5
Accepted
time: 140ms
memory: 16196kb

input:

200000 79994
2 35483
5 39827
12 56887
13 25533
15 153428
18 15164
19 11878
20 75339
24 119759
25 827...

output:

1
0
0
1
0
152209571
1
0
67846443
256867537
152510134
300997101
7831242
179751117
0
166369518
0
1
0
2...

result:

ok 79994 lines

Test #13:

score: 5
Accepted
time: 104ms
memory: 16624kb

input:

200000 10
1 18212
2 12539
6 113047
7 124259
11 181026
24 171770
26 106553
28 57953
31 167402
33 8548...

output:

465397042
593629129
798615913
424347866
321194689
757403436
468811817
227100827
255588579
815681185

result:

ok 10 lines

Test #14:

score: 5
Accepted
time: 117ms
memory: 16604kb

input:

200000 10
1 6332
3 82822
8 40816
9 82907
10 105786
12 44658
16 55833
23 38485
25 3392
26 88759
28 25...

output:

405675139
897537112
622929104
386104869
956720187
471636816
51478759
57111230
377734824
921982763

result:

ok 10 lines

Test #15:

score: 5
Accepted
time: 109ms
memory: 16600kb

input:

200000 10
2 159917
7 96456
8 37219
11 132388
15 34463
17 35571
21 315
22 67883
24 793
26 115757
28 8...

output:

453053254
185258202
909143733
615505893
541872704
788457111
758509860
663168261
581419346
206803769

result:

ok 10 lines

Test #16:

score: 5
Accepted
time: 128ms
memory: 16364kb

input:

200000 333
7 150698
8 45902
10 197132
12 46932
13 198593
14 42732
21 1877
22 188009
23 85556
25 1092...

output:

366312167
1819647
288818627
289251963
637379204
268258345
710678264
308430357
314485440
813323879
20...

result:

ok 333 lines

Test #17:

score: 5
Accepted
time: 141ms
memory: 16400kb

input:

200000 133
1 29089
4 118283
5 54192
6 124551
9 82454
11 16278
16 151949
18 51321
19 94155
26 145653
...

output:

74490490
128961041
324286623
565693061
204610350
590648521
715421578
783927827
550419967
791296597
2...

result:

ok 133 lines

Test #18:

score: 5
Accepted
time: 124ms
memory: 16392kb

input:

200000 262
7 158500
12 144061
18 48427
20 77748
21 175177
22 121943
25 89477
29 3820
31 13537
37 301...

output:

325846007
445365531
265881246
901849563
408346699
574041293
314978805
300077023
58626797
365208812
6...

result:

ok 262 lines

Test #19:

score: 5
Accepted
time: 149ms
memory: 16448kb

input:

200000 212
4 5924
5 68470
6 34717
8 39714
11 23683
14 169146
15 34814
29 152118
33 46998
35 6733
39 ...

output:

87378768
897377073
292438843
214404930
363649283
255682178
962771228
120043816
74310682
438997094
98...

result:

ok 212 lines

Test #20:

score: 5
Accepted
time: 151ms
memory: 16432kb

input:

200000 214
1 29911
16 121241
20 36766
24 85712
25 150205
29 7071
30 187675
31 153914
36 124592
40 16...

output:

988959638
449591
606050087
103906883
365178401
804421442
400944302
851325297
502059046
544860612
589...

result:

ok 214 lines

Extra Test:

score: 0
Extra Test Passed