QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556873#6737. Neighbourhood251SecAC ✓5439ms70388kbC++144.6kb2024-09-10 21:44:542024-09-10 21:44:54

Judging History

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

  • [2024-09-10 21:44:54]
  • 评测
  • 测评结果:AC
  • 用时:5439ms
  • 内存:70388kb
  • [2024-09-10 21:44:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 800;
struct Edge {
	int v, nxt;
} e[400005];
int head[200005], len = 1;
void Insert(int u, int v) {
	e[++len] = { v, head[u] };
	head[u] = len;
}
int n, q;
int dpt[200005], lt[200005], rt[200005], cti, st[20][200005], prt[200005];
ll we[200005];
namespace Blk {
	const int B = 500;
	int bel[200005], blt[5005], brt[5005];
	ll tg[5005], a[200005];
	void Init() {
		for (int i = 1; i <= n; i++) {
			bel[i] = (i + B - 1) / B;
			if (!blt[bel[i]]) blt[bel[i]] = i;
			brt[bel[i]] = i;
		}
	}
	void M(int l, int r, ll w) {
		if (bel[l] == bel[r]) {
			for (int i = l; i <= r; i++) a[i] += w;
		}
		else {
			for (int i = bel[l] + 1; i < bel[r]; i++) tg[i] += w;
			for (int i = l; i <= brt[bel[l]]; i++) a[i] += w;
			for (int i = blt[bel[r]]; i <= r; i++) a[i] += w;
		}
	}
	ll Q(int i) { return tg[bel[i]] + a[i]; }
	void Modify(int u, ll w) { M(lt[u], rt[u], w); }
	ll Query(int u) { return Q(lt[u]); }
}
void DFS(int u, int fa) {
	st[0][lt[u] = ++cti] = prt[u] = fa;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa) continue;
		dpt[i >> 1] = v;
		DFS(v, u);
		Blk::Modify(v, we[i >> 1]);
	}
	rt[u] = cti;
}
int PMin(int u, int v) { return lt[u] < lt[v] ? u : v; }
void PreST() {
	for (int j = 1; j < 20; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			st[j][i] = PMin(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
}
int LCA(int u, int v) {
	if (u == v) return u;
	if ((u = lt[u]) > (v = lt[v])) swap(u, v);
	int x = __lg(v - u++);
	return PMin(st[x][u], st[x][v - (1 << x) + 1]);
}
int ubn[200005], dbn[200005];
vector<int> clu[200005], bn;
namespace TopCluster {
	int ccl[200005], ccnt, st[200005], top;
	void AddCl(int u, int v) {
		if (!v) v = ccl[ccnt];
		for (int i = 1; i <= ccnt; i++) {
			int r = ccl[i];
			ubn[r] = u, dbn[r] = v, clu[v].push_back(r);
		}
		ccnt = 0;
	}
	int wai[200005], rec[200005], ctp[200005];
	void DFS(int u, int fa) {
		ctp[u] = top, wai[u] = 1;
		int bcnt = 0;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (v == fa) continue;
			st[++top] = v;
			DFS(v, u);
			wai[u] += wai[v];
			if (rec[v]) rec[u] = rec[v], bcnt++;
		}
		if (wai[u] > B || bcnt > 1 || !fa) {
			wai[u] = 0, rec[u] = u;
			int j = ctp[u] + 1, cnt = 0, cdn = 0;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].v;
				if (v == fa) continue;
				if (cnt + wai[v] > B || (rec[v] && cdn)) {
					for (; j < ctp[v] && j <= top; j++) ccl[++ccnt] = st[j];
					AddCl(u, cdn), cdn = cnt = 0;
				}
				cnt += wai[v];
				if (rec[v]) cdn = rec[v];
			}
			for (; j <= top; j++) ccl[++ccnt] = st[j];
			if (u == 1) ccl[++ccnt] = 1;
			AddCl(u, cdn);
			top = ctp[u];
		}
	}
}
ll du[200005], dd[200005];
vector<int> pu[200005], pd[200005];
ll D(int u, int v) {
	return Blk::Query(u) + Blk::Query(v) - 2 * Blk::Query(LCA(u, v));
}
void Modify(int x, ll y) {
	Blk::Modify(dpt[x], y - we[x]);
	we[x] = y;
	int b = dbn[dpt[x]], a = ubn[b];
	for (auto i : clu[b]) {
		du[i] = D(i, a); dd[i] = D(i, b);
	}
	sort(pu[b].begin(), pu[b].end(), [](int x, int y) {
		return du[x] < du[y];
	});
	sort(pd[b].begin(), pd[b].end(), [](int x, int y) {
		return dd[x] < dd[y];
	});
}
int Query(int x, ll y) {
	int ans = 0;
	for (auto u : clu[dbn[x]]) {
		if (D(u, x) <= y) ans++;
	}
	for (auto u : bn) {
		if (u == dbn[x]) continue;
		ll da = D(ubn[u], x), db = D(u, x);
		if (da < db) {
			du[n + 1] = y - da;
			ans += upper_bound(pu[u].begin(), pu[u].end(), n + 1, [](int x, int y) {
				return du[x] < du[y];
			}) - pu[u].begin();
		}
		else {
			dd[n + 1] = y - db;
			ans += upper_bound(pd[u].begin(), pd[u].end(), n + 1, [](int x, int y) {
				return dd[x] < dd[y];
			}) - pd[u].begin();
		}
	}
	return ans;
}
int main() {
	scanf("%d%d", &n, &q);
	Blk::Init();
	for (int i = 1, u, v, w; i < n; i++) {
		scanf("%d%d%d", &u, &v, &w);
		Insert(u, v), Insert(v, u);
		we[i] = w;
	}
	DFS(1, 0), PreST(), TopCluster::DFS(1, 0);
	for (int i = 1; i <= n; i++) {
		bn.push_back(dbn[i]);
		pu[i] = pd[i] = clu[i];
	}
	sort(bn.begin(), bn.end());
	bn.erase(unique(bn.begin(), bn.end()), bn.end());
	for (int x : bn) {
		int b = x, a = ubn[b];
		for (auto i : clu[x]) {
			du[i] = D(i, a); dd[i] = D(i, b);
		}
		sort(pu[b].begin(), pu[b].end(), [](int x, int y) {
			return du[x] < du[y];
		});
		sort(pd[b].begin(), pd[b].end(), [](int x, int y) {
			return dd[x] < dd[y];
		});
	}
	while (q--) {
		int op, x; ll y; scanf("%d%d%lld", &op, &x, &y);
		if (op == 1) Modify(x, y);
		else printf("%d\n", Query(x, y));
	}
	return 0;
}

詳細信息

Test #1:

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

input:

3 7
1 2 3
2 3 1
2 2 1
2 1 3
2 3 4
1 1 1
2 2 1
2 1 0
2 3 1

output:

2
2
3
3
1
2

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 3479ms
memory: 70388kb

input:

200000 200000
1 2 146181238
2 3 45037818
3 4 176924060
4 5 969365276
5 6 683948619
6 7 356268194
7 8 871634797
8 9 630254480
9 10 283061123
10 11 204904965
11 12 838381393
12 13 516373812
13 14 253862710
14 15 223572474
15 16 114452997
16 17 145251056
17 18 905638436
18 19 375445402
19 20 549829545
...

output:

219
62303
1358
5532
65345
682
11856
120285
4980
5689
2998
2314
18102
8014
20512
2827
113022
74534
159775
14517
17961
21855
8138
265
3336
3251
7023
35187
4932
151611
14338
101
899
117
64441
888
10380
1833
29381
1014
4806
10770
23734
236
37258
2280
14550
2196
38205
80950
80839
4517
74570
13972
95914
7...

result:

ok 99572 numbers

Test #3:

score: 0
Accepted
time: 2949ms
memory: 70020kb

input:

200000 200000
1 2 656062236
2 3 261234277
3 4 723980474
4 5 755233101
5 6 542749909
6 7 9519713
7 8 878661582
8 9 402365775
9 10 9875710
10 11 894863180
11 12 4247155
12 13 287336772
13 14 76881950
14 15 132946165
15 16 174895351
16 17 93681141
17 18 504958771
18 19 372774409
19 20 406716610
20 21 2...

output:

60189
5717
13802
2030
71980
20394
75205
11241
1388
104056
11760
588
4319
49744
8187
29084
507
39561
2286
3138
42602
77393
15811
5709
15417
48109
9596
846
16875
27181
52
11525
5741
2476
34614
4877
24002
85119
171
246
19408
89
806
42261
25552
865
158
70
3444
25736
60977
4454
11905
126842
35189
3858
15...

result:

ok 180067 numbers

Test #4:

score: 0
Accepted
time: 3882ms
memory: 70256kb

input:

200000 200000
1 2 111377160
2 3 892685763
3 4 889507841
4 5 901236774
5 6 834278466
6 7 298553149
7 8 8150218
8 9 390360541
9 10 621635057
10 11 699702261
11 12 606252166
12 13 657657482
13 14 274827098
14 15 206330963
15 16 546124412
16 17 888769586
17 18 921510546
18 19 117645637
19 20 919234429
2...

output:

171
20066
102752
6642
68416
1708
644
62536
7246
7441
3463
13905
613
38743
54559
8959
4615
103272
40246
26304
149
44249
212
123
34390
82218
521
85028
17557
1014
17048
2759
3173
5518
3043
1266
22438
83793
218
27248
24662
134581
9800
16393
39893
727
13548
3
2669
26080
573
411
9172
3642
2111
19478
563
4...

result:

ok 20072 numbers

Test #5:

score: 0
Accepted
time: 5439ms
memory: 54420kb

input:

200000 200000
1 2 657504560
1 3 539914646
2 4 617534421
2 5 145385645
4 6 11287875
4 7 472341345
1 8 114534025
4 9 940656797
5 10 806152132
3 11 623707008
2 12 841303670
10 13 804880741
1 14 35219013
12 15 924229426
2 16 834808041
5 17 118952529
1 18 561626985
9 19 884416843
10 20 604788348
18 21 11...

output:

605
131
199697
199999
34
3
36514
256
21
2
261
181731
199877
199991
3229
6
122767
4374
200000
53327
40
4
7858
175711
200000
132026
169165
72
112
120267
171500
1
95691
36697
199851
200000
6940
662
200000
1
1168
2
200000
19
16
211
9
11
196444
85
42751
200000
11
200000
115222
28279
177665
691
127
197292...

result:

ok 100112 numbers

Test #6:

score: 0
Accepted
time: 4211ms
memory: 54928kb

input:

200000 200000
1 2 525193329
1 3 693042313
1 4 194485999
1 5 319160289
1 6 925926764
1 7 592828271
1 8 262594959
1 9 60806042
1 10 704487773
1 11 963570483
1 12 71530643
1 13 66914391
1 14 933028716
1 15 678371635
1 16 714555824
1 17 507124524
1 18 160041085
1 19 769379790
1 20 938594863
1 21 2405638...

output:

85288
1
28130
1
170364
1
5907
1
71883
1
184882
1
1
1
70569
200000
128205
44921
20408
1
82605
17646
1
1
1
1
22715
1
145387
1
161039
175478
1
200000
105070
1
19679
134568
200000
29028
72699
79367
1
4346
111703
200000
200000
200000
1
1
19607
49417
109205
200000
77104
200000
200000
1
1
1
200000
28475
74...

result:

ok 179761 numbers

Test #7:

score: 0
Accepted
time: 4154ms
memory: 54928kb

input:

200000 200000
1 2 796456214
2 3 740604027
3 4 363664601
4 5 815797615
5 6 463286014
6 7 430082206
7 8 639881106
8 9 14913310
9 10 887879247
10 11 796246680
11 12 802527015
12 13 437002899
13 14 281562336
14 15 688457701
15 16 905558374
16 17 617631127
17 18 193398033
18 19 642019042
19 20 610926873
...

output:

1
94
136
110084
136
35645
135676
200000
38729
11501
9
16200
393
146
132
199986
50
10840
5194
99022
19
150100
200000
11
60695
1673
3
166621
36
98
44
7
7
200000
3055
27
65
27000
47
15214
842
1
41870
17
3213
26
175965
5
99
41
131613
199989
108859
1078
73
35
82388
34
10145
1
1
3
6
31
36
139
199995
46667...

result:

ok 100168 numbers

Test #8:

score: 0
Accepted
time: 594ms
memory: 59120kb

input:

100000 30000
1 2 232632894
2 3 615573029
3 4 812551786
4 5 161942260
5 6 457428876
6 7 89411628
7 8 402198074
8 9 266513672
9 10 866030976
10 11 357259122
11 12 903193100
12 13 702113698
13 14 49435177
14 15 402399859
15 16 280341727
16 17 222276068
17 18 8665747
18 19 33844315
19 20 112069486
20 21...

output:

21672
59783
1586
25348
1774
3133
29699
699
3686
2318
1797
5456
1494
2998
8846
4732
1492
14933
5263
37596
16672
4
8662
1768
20587
70040
100000
9272
10659
25123
16087
1168
1734
144
10726
595
5020
1771
6064
6480
40169
11797
89942
99074
19569
433
5336
764
5706
40
73256
2012
25177
57183
3743
100000
4379
...

result:

ok 2958 numbers

Test #9:

score: 0
Accepted
time: 587ms
memory: 49004kb

input:

100000 30000
1 2 190746238
2 3 675029592
1 4 168040323
1 5 922467464
5 6 361179444
6 7 34395123
1 8 410124233
5 9 960812805
7 10 622220798
1 11 958352127
8 12 38660819
4 13 810644242
13 14 855144641
12 15 329318635
2 16 114496731
9 17 522298672
3 18 557815746
7 19 476566127
19 20 353005409
17 21 438...

output:

3327
96746
100000
100000
2
99459
25780
6
1364
3681
2
99982
21494
100000
100000
648
71
39
99579
100000
2
100000
37698
30633
312
12
29977
100000
100000
15
1
29
1926
4
100000
64460
396
100000
8099
54
511
98678
42
751
489
954
1
1
7206
178
47644
99588
3352
44594
1
100000
62862
1265
4682
412
22
26
100000
...

result:

ok 14890 numbers

Test #10:

score: 0
Accepted
time: 417ms
memory: 49772kb

input:

100000 30000
1 2 354831917
1 3 202905598
1 4 611619647
1 5 20222478
1 6 708756128
1 7 821129867
1 8 893394198
1 9 626738967
1 10 176378473
1 11 54191181
1 12 558850835
1 13 18618138
1 14 713989739
1 15 837205587
1 16 94638856
1 17 662322139
1 18 66448477
1 19 615697398
1 20 259837281
1 21 93808179
1...

output:

1
62583
1
1
100000
93793
64328
100000
1
75867
34018
3072
1
1
91692
94061
2578
1
72165
44133
96303
1
1
100000
3013
78870
43017
87852
1
100000
46541
1
359
30700
100000
26805
1
70202
100000
100000
1
1
33742
92761
100000
55185
28767
100000
90214
100000
35616
1
100000
100000
1
1
2216
100000
15849
1
1
311...

result:

ok 26958 numbers

Test #11:

score: 0
Accepted
time: 443ms
memory: 49780kb

input:

100000 30000
1 2 104249460
2 3 478232035
3 4 466312804
4 5 189561732
5 6 362119693
6 7 53996994
7 8 566013752
8 9 731486787
9 10 923017604
10 11 520020314
11 12 598450495
12 13 772432347
13 14 65082675
14 15 905376194
15 16 112445962
16 17 449717550
17 18 624966046
18 19 300208577
19 20 198329359
20...

output:

28
7
20
155
51
24492
23685
30
133
14700
204
50775
50177
114
532
83
2884
27
20855
23
117
194
139
67820
36
31788
27
100000
142
186
4
10014
6
7942
1
100000
132
73715
10
74
160
66725
11
100000
100000
22
57463
15280
303
35136
51
65
556
113
34054
24
851
20527
1101
54
45368
3
42
702
11
35
3762
3
93588
8
58...

result:

ok 15102 numbers

Test #12:

score: 0
Accepted
time: 499ms
memory: 56772kb

input:

100000 30000
1 2 793126017
2 3 232330993
3 4 449065337
4 5 490733472
5 6 111589134
6 7 668100127
7 8 821095971
8 9 285891331
9 10 902446109
10 11 449050951
11 12 520804843
12 13 640551484
13 14 545522531
14 15 371179414
15 16 413586021
16 17 396937695
17 18 796739570
18 19 326494170
19 20 769171110
...

output:

54598
7234
2670
42497
20235
1707
178
12828
7636
8991
100000
6821
11643
35392
52297
39388
5538
30741
524
83977
1168
58757
8619
10299
4380
7501
13833
35865
193
19087
3646
38201
123
369
100000
12576
2484
23287
95
14638
2205
19
8385
5045
11518
27273
96810
39236
31815
48670
3476
10351
23503
100000
1234
1...

result:

ok 14953 numbers

Test #13:

score: 0
Accepted
time: 349ms
memory: 60084kb

input:

100000 30000
1 2 914076278
2 3 849075708
3 4 838143543
4 5 395635779
5 6 178103168
6 7 238090750
7 8 485456169
8 9 96798738
9 10 953953655
10 11 753633712
11 12 310722446
12 13 434513796
13 14 146296271
14 15 7536252
15 16 234163959
16 17 265914804
17 18 819483810
18 19 31553002
19 20 659460957
20 2...

output:

29412
26523
56269
58437
2301
695
2265
5556
13671
5033
74
1205
2475
11967
10762
62
413
1799
47885
466
167
102
8973
83448
7401
1503
3632
199
46638
56906
27
27503
11561
25788
27150
18473
6389
3730
20391
1750
41898
2025
23885
52
2273
22550
483
31639
15507
34642
26231
11512
53564
17996
2041
14127
8179
14...

result:

ok 27055 numbers

Test #14:

score: 0
Accepted
time: 4270ms
memory: 54132kb

input:

200000 200000
1 2 462099758
1 3 866972101
2 4 996540461
2 5 578524349
3 6 571095940
3 7 703136877
4 8 666580508
4 9 285459002
5 10 814201161
5 11 660727584
6 12 654376807
6 13 837770648
7 14 714870560
7 15 104972922
8 16 32803231
8 17 735694895
9 18 110658827
9 19 889606190
10 20 17130278
10 21 4067...

output:

200000
67686
200000
200000
200000
200000
200000
630
1
200000
200000
1
31346
1
200000
200000
561
5
1
200000
200000
200000
200000
26451
200000
200000
4
200000
200000
16916
200000
200000
153875
200000
200000
200000
200000
269
25
200000
200000
200000
200000
1
5742
200000
200000
200000
113574
200000
2942...

result:

ok 100022 numbers

Test #15:

score: 0
Accepted
time: 3421ms
memory: 55580kb

input:

200000 200000
1 2 267010287
2 3 167068641
3 4 926147815
4 5 278208820
5 6 739843382
6 7 662489052
7 8 868323923
8 9 370708651
9 10 197960447
10 11 453593839
11 12 593358148
12 13 867598178
13 14 321466717
14 15 531052203
15 16 684794512
16 17 86921369
17 18 272875802
18 19 77083057
19 20 244571756
2...

output:

468
89
102
5
41
491
207
198
288
307
197
143
57
275
168
5
34
150
151
87
221
634
7
69
181
80
17
49
41
49
60
1323
1815
1179
981
28
922
234
38
124
25
459
406
1122
37
239
375
645
144
28
367
69
1168
413
33
43
305
422
26
30
2
668
2436
45
31
810
17
113
267
1
467
208
38
68
22
284
132
286
7
22
9
7
346
249
1
9...

result:

ok 99810 numbers

Test #16:

score: 0
Accepted
time: 3565ms
memory: 54464kb

input:

200000 200000
1 2 530262027
1 3 577167565
1 4 991638279
1 5 867902762
1 6 49113833
1 7 636751479
1 8 757930507
1 9 457909927
1 10 811776506
1 11 92479382
1 12 668573430
1 13 368351521
1 14 482946458
1 15 716207055
1 16 734689871
1 17 469203061
1 18 436245204
1 19 936484001
1 20 650565287
1 21 981462...

output:

543
17908
18325
96565
6039
60319
9138
32634
38869
163527
5272
67242
16885
41840
19723
40571
12028
8596
9708
671
165873
38146
17699
22998
242
24416
18562
5659
34
1
2340
91317
16323
17238
4040
98902
6897
13092
38011
12305
31218
105668
1
368
1881
11920
24287
37200
28287
18319
14607
15748
39054
49303
13...

result:

ok 99822 numbers

Test #17:

score: 0
Accepted
time: 3865ms
memory: 54468kb

input:

200000 200000
1 2 747157235
1 3 495557667
1 4 557250681
1 5 373058000
1 6 330210729
1 7 842153828
1 8 834790086
1 9 82820423
1 10 234384256
1 11 169048934
1 12 554053879
1 13 656281805
1 14 245175239
1 15 15339182
1 16 130032764
1 17 634709406
1 18 507167281
1 19 522574826
1 20 757475198
1 21 875842...

output:

19849
96
49
1
47
779
74734
110653
87
147530
12843
3
8
32643
76190
78606
27368
8535
56
3733
2420
2
42669
2746
200000
21675
18
5584
1708
2254
27
1
70122
406
203
81795
17262
61177
204
107338
80699
4146
2230
8855
3109
104314
3992
1424
399
14894
28
7
200000
39416
43093
11
20664
32
6760
57702
71
2851
82
8...

result:

ok 99760 numbers