UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203296#3557. 平衡树snow_trace1004076ms48200kbC++113.3kb2024-02-22 09:30:052024-02-22 13:03:52

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int dfn[200005];
vector<int>p[200005];
struct node{
	int l,r,sum,lazy;
	void add(int x){
		if(x == 1)sum = r-l,lazy = 1;
		if(x == -1)sum =0 ,lazy =-1;
	}
}tree[1000005];
void push_up(int k){
	tree[k].sum = tree[k<<1].sum+tree[k<<1|1].sum;
}void push_down(int k){
	if(tree[k].lazy!=0){
		tree[k<<1].add(tree[k].lazy),tree[k<<1|1].add(tree[k].lazy);tree[k].lazy = 0;
	}
}void build(int l,int r,int k){
	tree[k].l =l ,tree[k].r = r;
	if(l+1 == r){
		return;
	}build(l,l+r>>1,k<<1),build(l+r>>1,r,k<<1|1);
}void update(int l,int r,int k,int add){
	int ll = tree[k].l,rr = tree[k].r;
	if(l>=rr or ll>=r)return;
	if(l<=ll and rr<=r){
		tree[k].add(add);return;
	}push_down(k);
	update(l,r,k<<1,add),update(l,r,k<<1|1,add);
	push_up(k);
}int query(int l,int r,int k){
	int ll= tree[k].l,rr = tree[k].r;
	if(l>=rr or ll>=r)return 0;
	if(l<=ll and rr<=r)return tree[k].sum;
	push_down(k);
	return query(l,r,k<<1)+query(l,r,k<<1|1);
}
int x[200005],y[200005],fa[200005],dep[200005],sz[200005];int nw=0;
void dfs1(int now,int f){
	fa[now] = f;dep[now] = dep[f]+1;dfn[now] = ++nw;sz[now] = 1;
	for(int i =0;i<p[now].size();i++){
		if(p[now][i] == f)continue;dfs1(p[now][i],now);sz[now]+=sz[p[now][i]];
	}return;
}int k,s;
int a[200005],tt[200005];
bool cmp(int a,int b){
	return dep[a]<dep[b];
}
#define lowbit(x) x&(-x)
int Tree[200005];
void upd(int pos,int add){
	for(int i = pos;i<=n;i+=lowbit(i))Tree[i]+=add;
}int qquery(int pos){
	int res =0;for(int i = pos;i>0;i-=lowbit(i))res+=Tree[i];return res;
}
void solve(){
	cin >> k;
	for(int i = 1;i<=k;i++){
		int aa;cin >> aa;
		if(dep[x[aa]]>dep[y[aa]])a[i] = x[aa];else a[i] = y[aa];
	}sort(a+1,a+1+k,cmp);cin>> s;
	update(1,n+1,1,-1);
	vector<int>pf,ps;
//	for(int i = 1;i<=k;i++){
//		if(query(dfn[a[i]],dfn[a[i]]+sz[a[i]],1) == 0){
//			pf.push_back(a[i]);
//			update(dfn[a[i]],dfn[a[i]]+sz[a[i]],1,1);
//		}
//	}
	update(1,n+1,1,-1);
//	for(int i= 1;i<=n;i++)cout<< query(i,i+1,1) << " ";cout << endl;
	for(int i =k;i>=1;i--){
		if(query(dfn[a[i]],dfn[a[i]]+sz[a[i]],1) == 0){
			ps.push_back(a[i]);
			update(dfn[a[i]],dfn[a[i]]+sz[a[i]],1,1);upd(dfn[a[i]],1);
		}
	}int l = 0,r = s;int mxx =0 ;
	for(int i = 1;i<=k;i++)mxx = max(mxx,qquery(dfn[a[i]]+sz[a[i]]-1)-qquery(dfn[a[i]]-1));
	for(int x:ps)upd(dfn[x],-1);
	//cout << mxx << " " << ps.size() << endl;
	while(l<r){
	//	cout << 111 << endl;
		int mid = l+r>>1;
		/*
			x-(n-x)<=s
			2x-n<=s
			x<=(n+s)/2
			(n-x)-x<=s
			n-2x<=s
			2x>=n-s
			x>=(n-s)/2
		*/
		int mn = (s-mid+1)/2,mx = (s+mid)/2;
	//	cout << " " << s << " " << mid << " " << mn << " " << mx << endl;
		if(mn*mxx>mx or mn*ps.size()>s)l = mid+1;
		else r = mid;
	}cout << r << '\n';
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>> n >> q;
	for(int i = 1;i<n;i++){
		int a,b;cin >> a >> b;
		x[i] = a,y[i] =b;p[a].push_back(b),p[b].push_back(a);
	}dfs1(1,1);build(1,n+1,1);
	while(q--){
		solve();
	} 
	return 0;
}
/*
建虚树然后二分答案。
不想建虚树怎么办?
其实只需要先把极端的点都预处理出来。 
先预处理出叶子节点
我们考虑让子树的size在满足条件的情况下尽可能的小
然后把多余的点全部丢给1
  
*/

详细

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

Test #1:

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

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: 5992kb

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: 6312kb

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: 4ms
memory: 6308kb

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: 0ms
memory: 6308kb

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: 4ms
memory: 6304kb

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: 156ms
memory: 48156kb

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: 133ms
memory: 48200kb

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: 375ms
memory: 40636kb

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: 395ms
memory: 40628kb

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: 406ms
memory: 40632kb

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: 386ms
memory: 40612kb

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: 243ms
memory: 41684kb

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: 254ms
memory: 41648kb

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: 228ms
memory: 41864kb

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: 342ms
memory: 41256kb

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: 331ms
memory: 41260kb

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: 285ms
memory: 41268kb

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: 268ms
memory: 41332kb

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: 263ms
memory: 41396kb

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