UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204048#564. 多重集合问题snow_trace10010058ms340132kbC++113.1kb2024-04-06 10:10:192024-04-06 12:11:24

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dep[200005],lca[200005][19],dfn[200005],ssz[200005];
vector<int>p[200005];
int trie[40000005][2];long long sz[40000005];int nw = 0;
struct node{
	int l,r,rt;
}tree[800005];
inline void ins(int now,int x,int k){
	sz[now]+=k;
	for(int i = 29;i>=0;i--){
		bool a = x>>i&1;
		if(!trie[now][a])trie[now][a] = ++nw;
		now = trie[now][a];sz[now]+=k;
	}
}inline long long query(int now,int a,int b){
	long long ans = 0;
	//cout << "  " << now << " " << a << " " << b << endl;
	for(int i = 29;i>=0;i--){if(!now)break;
		bool aa = a>>i&1,bb = b>>i&1;
	//	cout << " " << aa << " " << bb << endl;
		if(bb == 0){
			now = trie[now][aa];
		}else{
		//	cout << "   " << trie[now][a] << " " << sz[trie[now][aa]] << endl;
			ans+=sz[trie[now][aa]];now = trie[now][1^aa];
		}
	}return ans+sz[now];
	//x^a<b
}
void build(int l,int r,int k){
	tree[k].l = l,tree[k].r = r;
	tree[k].rt = ++nw;
	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 x,int nn,int k){
	int ll = tree[k].l,rr = tree[k].r;
	if(ll>=r or l>=rr)return;
	if(l<=ll and rr<=r){
		ins(tree[k].rt,x,nn);return;
	}update(l,r,x,nn,k<<1),update(l,r,x,nn,k<<1|1);
}long long qquery(int pos,int k,int a,int b){
	int l = tree[k].l,r = tree[k].r;
	long long rr = query(tree[k].rt,a,b);
	if(l+1 == r)return rr;
	int mid =l +r>>1;
	if(pos<mid)return qquery(pos,k<<1,a,b)+rr;
	return qquery(pos,k<<1|1,a,b)+rr;
}
int cc;
void dfs(int now,int fa){
	ssz[now] = 1,dep[now] = dep[fa]+1,dfn[now] = ++cc;
	lca[now][0] = fa;for(int i = 1;i<=18;i++)lca[now][i] = lca[lca[now][i-1]][i-1];
	for(int i= 0;i<p[now].size();i++){
		if(p[now][i] == fa)continue;
		dfs(p[now][i],now);ssz[now]+=ssz[p[now][i]];
	}
}int kth(int x,int k){
	for(int i =0;k;k>>=1,i++)if(k&1)x = lca[x][i];return x;
}
int lcaa(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int dis = dep[x]-dep[y];
	for(int i =0;dis;dis>>=1,i++)if(dis&1)x = lca[x][i];
	if(x == y)return x;
	for(int i = 18;i>=0;i--){
		if(lca[x][i]!=lca[y][i]){
			x = lca[x][i],y = lca[y][i];
		}
	}return lca[x][0];
}int nrt = 1;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i<n;i++){
		int a,b;cin >> a >> b;
		p[a].push_back(b),p[b].push_back(a);
	}dfs(1,1);build(1,n+1,1);
	int q;cin >> 	q;
	while(q--){
		int op;cin >> op;
		if(op == 1){
			//假如在根和1之间需要特判
			int v,x,k;cin >> v >> x >> k;
			if(lcaa(nrt,v) == v){
				update(1,n+1,x,k,1);
				if(v == nrt){
					continue;
				}
				int nxt = kth(nrt,abs(dep[nrt]-dep[v])-1);
				update(dfn[nxt],dfn[nxt]+ssz[nxt],x,-k,1);
			}else{
				update(dfn[v],dfn[v]+ssz[v],x,k,1);
			}
		}if(op == 2){
			int v,a,b;cin >> v >> a >> b;
			long long ans = qquery(dfn[v],1,a,b);
			cout << ans << '\n';
		}if(op == 3){
			cin >> nrt;
		}
	}
	return 0;
}/*
这么大的 DS 题你不给我大洋里我写牛魔呢 /wx/wx/wx
线段树套 trie,换根很套路。

4
1 2
1 3
3 4
14
1 1 1 1
1 2 2 1
1 3 3 1
2 1 0 4
2 2 1 3
2 4 3 2
3 4
1 3 3 1
1 4 4 1
1 1 1 1
1 2 2 1
2 1 0 4
2 2 1 3
2 4 3 2

1
2
1 1 3 2
2 1 1 2
*/

详细

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

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 6ms
memory: 6488kb

input:

500
244 90
412 244
93 412
488 90
79 93
340 412
207 340
408 93
452 79
200 79
182 408
424 79
157 182
8...

output:

0
0
0
0
0
0
566198873
88418523
0
447687853
417410646
88418523
1138954231
252822794
0
0
88418523
0
0
...

result:

ok 58 tokens

Test #2:

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

input:

500
183 146
183 144
183 397
397 32
32 95
144 233
233 254
397 247
95 309
247 81
254 24
24 424
24 482
...

output:

0
356895596
0
653090121
1260518543
0
2187569813
1536809911
653090121
4346333812
2934191048
280676296...

result:

ok 51 tokens

Test #3:

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

input:

2
2 1
500
1 2 341404994 582616173
1 1 37451687 382659157
1 2 386934479 438560511
1 2 61268050 701143...

output:

2599988434
7706270673
17290581682
33614581607
34031096649
2608282159
10908180780
30251498013
1290000...

result:

ok 52 tokens

Test #4:

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

input:

13
12 3
3 11
12 4
11 9
11 2
9 10
9 6
4 7
2 1
7 13
6 8
6 5
500
1 3 325914127 283078917
1 13 627147976...

output:

2218191976
0
3542581422
3375269022
10620630750
6476407121
3243274252
6791312373
5510518139
188883967...

result:

ok 53 tokens

Test #5:

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

input:

500
45 290
147 290
88 45
226 45
313 290
423 88
344 423
288 45
46 226
107 313
108 313
330 290
73 344
...

output:

0
0
1311260699
1036424713
1036424713
1036424713
0
30392645
0
0
0
1418025799
1845009357
0
0
0
1036424...

result:

ok 46 tokens

Test #6:

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

input:

500
459 9
9 42
42 385
42 392
459 402
385 292
385 55
385 299
402 31
55 481
481 490
481 61
299 412
481...

output:

0
0
0
0
0
0
0
0
0
514099530
1315138132
0
1328932960
0
3703627416
795669584
5678344966
0
4154749998
2...

result:

ok 51 tokens

Test #7:

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

input:

280
249 69
83 249
34 249
210 34
32 249
136 210
159 249
246 136
166 249
176 246
121 159
230 69
108 34...

output:

0
687887638
0
707352338
588720084
19464700
687887638
19464700
1103264581
687887638
1469726377
191502...

result:

ok 45 tokens

Test #8:

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

input:

430
325 30
325 41
41 185
325 404
185 417
404 299
404 348
299 407
348 84
299 378
407 152
84 339
407 3...

output:

0
0
698742390
0
252808268
0
0
0
2568472240
1490064534
1891821796
303962175
5860090068

result:

ok 13 tokens

Subtask #2:

score: 14
Accepted

Test #9:

score: 14
Accepted
time: 82ms
memory: 33368kb

input:

1
140000
2 1 576147149 772634763
1 1 396417010 92525865
1 1 991921618 1031225962
1 1 235592921 15079...

output:

0
10548880744
0
11035968403
0
434945668
4199008278
8554196900
11643712050
3509407981
16617382327
239...

result:

ok 13710 tokens

Test #10:

score: 0
Accepted
time: 159ms
memory: 33368kb

input:

1
140000
1 1 601243317 310785008
1 1 756350798 1070171392
1 1 809165721 925680784
1 1 62107755 55493...

output:

554935117
4586081606
11118112083
6054293998
5161117439
17530754643
25064513721
11410247010
407575270...

result:

ok 13742 tokens

Test #11:

score: 0
Accepted
time: 130ms
memory: 33380kb

input:

1
140000
2 1 85280416 820771523
1 1 1056295621 95349983
1 1 298938814 121898587
1 1 812343482 891760...

output:

0
3319311386
1397429405
0
13337569619
15666488362
5075202465
35432684863
42810838259
8230761582
3229...

result:

ok 13693 tokens

Test #12:

score: 0
Accepted
time: 74ms
memory: 33332kb

input:

1
140000
2 1 110343816 358921768
1 1 342487585 1072995510
1 1 116150149 16353409
1 1 638858316 22222...

output:

0
3046925655
818858034
18912173493
7628605816
3499749266
37357017239
3469268217
18016540602
35799368...

result:

ok 13899 tokens

Test #13:

score: 0
Accepted
time: 86ms
memory: 33356kb

input:

1
140000
1 1 135439984 970879372
1 1 702388605 976931981
1 1 1007070539 984550055
1 1 465373150 6263...

output:

0
15944697871
12194262560
4997618152
39398394529
40904079530
52545013433
63929272194
1434989091
4667...

result:

ok 13736 tokens

Test #14:

score: 0
Accepted
time: 67ms
memory: 33332kb

input:

1
140000
1 1 160503383 509062384
2 1 1062355161 880868453
1 1 824281873 879037645
1 1 291920753 1030...

output:

0
4475900441
4936679861
3195031318
16470492089
30164302445
39447055252
1341353668
34501618323
475292...

result:

ok 13953 tokens

Subtask #3:

score: 15
Accepted

Test #15:

score: 15
Accepted
time: 141ms
memory: 87772kb

input:

50000
23353 32918
23165 32918
42334 23165
37266 32918
36241 37266
48241 36241
30134 42334
5022 42334...

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
...

result:

ok 9729 tokens

Test #16:

score: 0
Accepted
time: 445ms
memory: 230140kb

input:

10000
8523 2979
8523 5212
8523 8063
5212 9095
9095 754
754 2186
9095 534
9095 8973
2186 1722
754 539...

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
...

result:

ok 13723 tokens

Test #17:

score: 0
Accepted
time: 141ms
memory: 62660kb

input:

140000
18963 105564
30407 18963
62244 18963
77218 105564
5670 18963
137321 62244
91120 62244
111337 ...

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
...

result:

ok 3902 tokens

Test #18:

score: 0
Accepted
time: 234ms
memory: 126876kb

input:

140000
110867 63174
63174 25637
63174 71796
63174 73409
73409 76383
25637 36626
36626 90597
76383 90...

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
...

result:

ok 3880 tokens

Test #19:

score: 0
Accepted
time: 455ms
memory: 134292kb

input:

140000
124760 17961
11053 124760
128007 124760
109257 124760
95880 128007
33568 128007
91823 11053
1...

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
...

result:

ok 13716 tokens

Test #20:

score: 0
Accepted
time: 851ms
memory: 335872kb

input:

140000
132301 113503
132301 8970
132301 71982
8970 38942
8970 75118
113503 37832
37832 111571
75118 ...

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
...

result:

ok 13686 tokens

Test #21:

score: 0
Accepted
time: 359ms
memory: 134764kb

input:

140000
9009 132135
103722 132135
66217 132135
138028 66217
132757 138028
3788 132757
139979 3788
450...

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
...

result:

ok 13767 tokens

Test #22:

score: 0
Accepted
time: 816ms
memory: 333688kb

input:

140000
74249 108669
74249 126812
74249 71764
74249 78093
71764 129403
71764 121546
129403 87766
8776...

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
...

result:

ok 13813 tokens

Subtask #4:

score: 23
Accepted

Test #23:

score: 23
Accepted
time: 142ms
memory: 52876kb

input:

50000
46569 8980
39271 8980
39589 46569
5017 39589
23140 5017
2759 8980
33776 46569
1593 33776
1461 ...

output:

0
0
0
0
0
0
0
39902982
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 4994 tokens

Test #24:

score: 0
Accepted
time: 254ms
memory: 118016kb

input:

50000
22404 4201
4201 46667
46667 34698
46667 39944
39944 40878
46667 20211
20211 35478
39944 17680
...

output:

933652152
0
2375845635
0
709713347
687670164
1355345803
3608644834
4952561203
709713347
8086571005
0...

result:

ok 5026 tokens

Test #25:

score: 0
Accepted
time: 143ms
memory: 52548kb

input:

50000
9822 28016
13645 9822
46865 13645
26017 46865
7350 46865
28109 26017
25795 46865
8982 7350
349...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
461880698
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 4994 tokens

Test #26:

score: 0
Accepted
time: 253ms
memory: 117608kb

input:

49999
22725 15994
15994 20311
15994 31578
20311 32700
20311 28270
32700 13245
20311 42919
42919 1559...

output:

499309076
499309076
529723643
2712007057
963524930
1270035832
1799759475
9812205988
0
7177810666
191...

result:

ok 4994 tokens

Test #27:

score: 0
Accepted
time: 77ms
memory: 51976kb

input:

50000
23427 7956
48134 7956
39627 7956
42939 23427
1263 42939
43960 7956
39891 42939
19124 42939
947...

output:

0
0
0
0
0
0
0
0
782916692
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
399414566
0
0
0
0
0
0
0
0
166482893
0
0
...

result:

ok 4939 tokens

Test #28:

score: 0
Accepted
time: 182ms
memory: 119328kb

input:

50000
29693 37097
29693 26099
29693 26661
37097 25535
26099 9909
37097 20408
26661 26364
9909 966
96...

output:

0
0
0
0
0
0
0
0
6097940120
1651113081
0
205287252
3892118560
7479546034
10442712552
2895904154
0
489...

result:

ok 5028 tokens

Subtask #5:

score: 21
Accepted

Test #29:

score: 21
Accepted
time: 80ms
memory: 52080kb

input:

50000
39387 7957
11949 39387
34768 39387
33546 34768
44523 34768
41098 7957
28433 7957
17150 7957
41...

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
1066342039
0
0
0
0
0
0
0
0
0...

result:

ok 4933 tokens

Test #30:

score: 0
Accepted
time: 163ms
memory: 115720kb

input:

49999
35918 22868
35918 7032
7032 36310
36310 12621
35918 49336
12621 41846
36310 18905
41846 13438
...

output:

677603658
677603658
1117450312
1666088414
0
3144959829
2328932306
1002358032
580923286
1925681320
64...

result:

ok 4900 tokens

Test #31:

score: 0
Accepted
time: 61ms
memory: 40720kb

input:

3000
2954 2434
2906 2434
2953 2954
2930 2953
2995 2953
2218 2930
801 2906
1659 2218
198 2906
1326 29...

output:

0
0
0
0
0
0
0
0
0
0
0
940816787
0
0
0
0
0
1023141047
1023141047
255064797
1963957834
1023141047
1023...

result:

ok 4910 tokens

Test #32:

score: 0
Accepted
time: 105ms
memory: 73520kb

input:

2000
1752 357
357 1591
1752 976
976 1803
1591 1429
357 1198
1198 576
576 17
1803 600
1198 1760
1760 ...

output:

0
0
0
648766211
0
421680852
0
149392927
149392927
0
0
3047694144
0
793131974
3770638680
0
4168551832...

result:

ok 4958 tokens

Test #33:

score: 0
Accepted
time: 94ms
memory: 51828kb

input:

50000
2764 5807
45488 5807
7579 2764
28703 5807
10247 2764
5171 7579
19758 5171
16625 5807
44789 757...

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
27365038...

result:

ok 4908 tokens

Test #34:

score: 0
Accepted
time: 250ms
memory: 116884kb

input:

50000
45220 36892
45220 20170
36892 17195
36892 31634
45220 40807
17195 38628
31634 19791
40807 3845...

output:

820550535
1118416783
0
1648529134
5967460758
2579160544
2011855989
4620324005
3645630996
3768063157
...

result:

ok 4875 tokens

Test #35:

score: 0
Accepted
time: 143ms
memory: 52112kb

input:

50000
45373 26713
15979 45373
25083 15979
23188 26713
21084 45373
1522 26713
26101 23188
42393 26713...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
599092872
0
0
0
0
0
0
0
0
0
0
599092872
0
0
0
0
0
0
0
0
0
0
0
7118...

result:

ok 4947 tokens

Test #36:

score: 0
Accepted
time: 312ms
memory: 116552kb

input:

50000
44176 34155
34155 11131
44176 15704
15704 23727
44176 47929
11131 35503
47929 9193
9193 16258
...

output:

482423793
0
0
0
0
913806153
736125415
0
1593504425
6764621961
1600443187
3958600150
0
3025771517
608...

result:

ok 4950 tokens

Subtask #6:

score: 20
Accepted

Test #37:

score: 20
Accepted
time: 398ms
memory: 134836kb

input:

140000
63337 114625
26384 114625
32063 114625
75167 63337
84354 32063
55609 84354
2313 84354
75757 6...

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
...

result:

ok 13774 tokens

Test #38:

score: 0
Accepted
time: 751ms
memory: 338852kb

input:

140000
27336 30368
30368 69843
30368 37026
37026 77396
30368 70989
69843 36739
77396 49374
49374 798...

output:

0
895826918
0
1221105604
162695280
2579993948
4343869477
987883548
4463791047
0
895826918
2429682906...

result:

ok 13757 tokens

Test #39:

score: 0
Accepted
time: 264ms
memory: 127048kb

input:

100000
59233 74815
85046 59233
57158 59233
83574 59233
99894 57158
64405 99894
12177 64405
76952 121...

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
...

result:

ok 13562 tokens

Test #40:

score: 0
Accepted
time: 813ms
memory: 331328kb

input:

140000
86512 71025
71025 58046
86512 137372
71025 49097
137372 133566
71025 136193
137372 27441
4909...

output:

0
0
0
0
971699863
5482565746
0
890462365
8063678010
1937213907
0
3145762434
11982563520
10081700216
...

result:

ok 13590 tokens

Test #41:

score: 0
Accepted
time: 481ms
memory: 134748kb

input:

140000
116172 95295
95107 95295
96592 116172
126232 96592
11299 95107
88780 95107
125782 11299
18949...

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
...

result:

ok 13597 tokens

Test #42:

score: 0
Accepted
time: 1036ms
memory: 340132kb

input:

140000
7209 64363
7209 43346
7209 9374
7209 67917
9374 3348
43346 73336
43346 85263
67917 123357
733...

output:

0
0
0
851958002
2151784985
1200990938
1056563582
2110067245
0
4521410217
6716703670
0
4593108547
407...

result:

ok 13609 tokens