#include "bits/stdc++.h"
using namespace std;
const int LIM = 100000;
#define fi first
#define se second
typedef long long LL;
typedef pair<LL, LL> PLL;
namespace DynamicDiameter {
vector <PLL> edge[LIM + 5];
int event[2 * LIM + 5];
int dfsTime = 0;
LL weights[LIM + 5], depth[LIM + 5];
PLL order[LIM + 5];
void eulerTour(int pos, int par = -1) {
dfsTime++;
order[pos].fi = dfsTime;
event[dfsTime] = pos;
for (auto &nx : edge[pos]) {
if (nx.fi == par) continue;
depth[nx.fi] = depth[pos] + nx.se;
weights[nx.fi] = nx.se;
eulerTour(nx.fi, pos);
dfsTime++;
event[dfsTime] = pos;
}
order[pos].se = dfsTime;
return;
}
const LL INF = 1e14;
// Segment Tree starts here
struct Node {
PLL maxDepth = {-INF, -1}, minDepth = {INF, -1};
PLL leftMax = {-INF, -1}, rightMax = {-INF, -1};
pair<LL, PLL> diameter = {-1, {-1, -1}};
LL lazy;
};
Node segt[8 * LIM + 5];
void pushDown(int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
if (segt[idx].lazy == 0) return;
auto &val = segt[idx].lazy;
segt[idx].maxDepth.fi += val;
segt[idx].minDepth.fi += val;
segt[idx].leftMax.fi -= val;
segt[idx].rightMax.fi -= val;
if (rangeL != rangeR) {
segt[idx * 2].lazy += val;
segt[idx * 2 + 1].lazy += val;
}
val = 0;
return;
}
void merge(Node &head, Node &l, Node &r) {
head.maxDepth = max(l.maxDepth, r.maxDepth);
head.minDepth = min(l.minDepth, r.minDepth);
head.leftMax = max(l.leftMax, r.leftMax);
head.leftMax = max(head.leftMax, {l.maxDepth.fi - 2 * r.minDepth.fi, l.maxDepth.se});
head.rightMax = max(l.rightMax, r.rightMax);
head.rightMax = max(head.rightMax, {r.maxDepth.fi - 2 * l.minDepth.fi, r.maxDepth.se});
head.diameter = max(l.diameter, r.diameter);
head.diameter = max(head.diameter, {l.maxDepth.fi + r.rightMax.fi, {l.maxDepth.se, r.rightMax.se}});
head.diameter = max(head.diameter, {r.maxDepth.fi + l.leftMax.fi, {r.maxDepth.se, l.leftMax.se}});
//~ cout << head.maxDepth << " " << head.minDepth << " " << head.leftMax << " " << head.rightMax << " " << head.diameter << endl;
}
void build(int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
//~ cout << rangeL << " " << rangeR << " " << idx << endl;
if (rangeL == rangeR) {
segt[idx].minDepth = segt[idx].maxDepth = {depth[event[rangeL]], event[rangeL]};
segt[idx].leftMax = segt[idx].rightMax = {-depth[event[rangeL]], event[rangeL]};
return;
}
int mid = (rangeL + rangeR) >> 1;
build(rangeL, mid, idx * 2);
build(mid + 1, rangeR, idx * 2 + 1);
merge(segt[idx], segt[idx * 2], segt[idx * 2 + 1]);
}
void update(int queryL, int queryR, LL val, int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
pushDown(rangeL, rangeR, idx);
if (rangeR < queryL) return;
if (queryR < rangeL) return;
if (queryL <= rangeL && rangeR <= queryR) {
segt[idx].lazy = val;
pushDown(rangeL, rangeR, idx);
return;
}
int mid = (rangeL + rangeR) >> 1;
update(queryL, queryR, val, rangeL, mid, idx * 2);
update(queryL, queryR, val, mid + 1, rangeR, idx * 2 + 1);
merge(segt[idx], segt[idx * 2], segt[idx * 2 + 1]);
return;
}
}
using namespace DynamicDiameter;
int main() {
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
LL n, q, w; cin >> n >> q >> w;
vector <PLL> edges(n - 1);
for (int i = 0; i < n - 1; i++) {
LL c;
cin >> edges[i].fi >> edges[i].se >> c;
edge[edges[i].fi].emplace_back(edges[i].se, c);
edge[edges[i].se].emplace_back(edges[i].fi, c);
}
eulerTour(1);
//~ for(int i = 1;i <= dfsTime;i++) cout << event[i] << " ";
//~ cout << endl;
//~ for(int i = 1;i <= n;i++) cout << i << " " << order[i].fi << " " << order[i].se << endl;
build();
LL ans = 0;
//~ cout << segt[1].diameter << endl;
//~ return 0;
while (q--) {
LL d, e; cin >> d >> e;
d = (d + ans) % (n - 1);
e = (e + ans) % w;
auto &edge = edges[d];
if (order[edge.fi].fi > order[edge.se].fi) {
swap(edge.fi, edge.se);
}
// Update the segment tree
//~ cout << e - weights[edge.se] << endl;
//~ cout << segt[1].diameter << endl;
update(order[edge.se].fi, order[edge.se].se, e - weights[edge.se]);
weights[edge.se] = e;
ans = segt[1].diameter.fi;
// auto curPair = segt[1].diameter.se;
// cout << curPair.fi << " " << curPair.se << endl;
cout << ans << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
79708 KB |
Output is correct |
2 |
Correct |
12 ms |
79708 KB |
Output is correct |
3 |
Correct |
11 ms |
79708 KB |
Output is correct |
4 |
Correct |
12 ms |
79960 KB |
Output is correct |
5 |
Correct |
11 ms |
79684 KB |
Output is correct |
6 |
Correct |
11 ms |
79668 KB |
Output is correct |
7 |
Correct |
12 ms |
79708 KB |
Output is correct |
8 |
Correct |
11 ms |
79708 KB |
Output is correct |
9 |
Correct |
11 ms |
79708 KB |
Output is correct |
10 |
Correct |
12 ms |
79708 KB |
Output is correct |
11 |
Correct |
12 ms |
79708 KB |
Output is correct |
12 |
Correct |
11 ms |
79708 KB |
Output is correct |
13 |
Correct |
11 ms |
79708 KB |
Output is correct |
14 |
Correct |
12 ms |
79660 KB |
Output is correct |
15 |
Correct |
12 ms |
79708 KB |
Output is correct |
16 |
Correct |
12 ms |
79648 KB |
Output is correct |
17 |
Correct |
11 ms |
79708 KB |
Output is correct |
18 |
Correct |
12 ms |
79660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
79708 KB |
Output is correct |
2 |
Correct |
12 ms |
79708 KB |
Output is correct |
3 |
Correct |
11 ms |
79708 KB |
Output is correct |
4 |
Correct |
12 ms |
79960 KB |
Output is correct |
5 |
Correct |
11 ms |
79684 KB |
Output is correct |
6 |
Correct |
11 ms |
79668 KB |
Output is correct |
7 |
Correct |
12 ms |
79708 KB |
Output is correct |
8 |
Correct |
11 ms |
79708 KB |
Output is correct |
9 |
Correct |
11 ms |
79708 KB |
Output is correct |
10 |
Correct |
12 ms |
79708 KB |
Output is correct |
11 |
Correct |
12 ms |
79708 KB |
Output is correct |
12 |
Correct |
11 ms |
79708 KB |
Output is correct |
13 |
Correct |
11 ms |
79708 KB |
Output is correct |
14 |
Correct |
12 ms |
79660 KB |
Output is correct |
15 |
Correct |
12 ms |
79708 KB |
Output is correct |
16 |
Correct |
12 ms |
79648 KB |
Output is correct |
17 |
Correct |
11 ms |
79708 KB |
Output is correct |
18 |
Correct |
12 ms |
79660 KB |
Output is correct |
19 |
Correct |
21 ms |
79704 KB |
Output is correct |
20 |
Correct |
21 ms |
79708 KB |
Output is correct |
21 |
Correct |
23 ms |
79708 KB |
Output is correct |
22 |
Correct |
21 ms |
79964 KB |
Output is correct |
23 |
Correct |
23 ms |
80220 KB |
Output is correct |
24 |
Correct |
28 ms |
80260 KB |
Output is correct |
25 |
Correct |
24 ms |
80220 KB |
Output is correct |
26 |
Correct |
25 ms |
80640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
79708 KB |
Output is correct |
2 |
Correct |
12 ms |
79720 KB |
Output is correct |
3 |
Correct |
15 ms |
79704 KB |
Output is correct |
4 |
Correct |
40 ms |
79708 KB |
Output is correct |
5 |
Correct |
153 ms |
80184 KB |
Output is correct |
6 |
Correct |
11 ms |
79704 KB |
Output is correct |
7 |
Correct |
12 ms |
79708 KB |
Output is correct |
8 |
Correct |
13 ms |
79904 KB |
Output is correct |
9 |
Correct |
15 ms |
79708 KB |
Output is correct |
10 |
Correct |
45 ms |
79956 KB |
Output is correct |
11 |
Correct |
165 ms |
80136 KB |
Output is correct |
12 |
Correct |
13 ms |
80216 KB |
Output is correct |
13 |
Correct |
14 ms |
80220 KB |
Output is correct |
14 |
Correct |
16 ms |
80524 KB |
Output is correct |
15 |
Correct |
46 ms |
80216 KB |
Output is correct |
16 |
Correct |
182 ms |
80588 KB |
Output is correct |
17 |
Correct |
39 ms |
88000 KB |
Output is correct |
18 |
Correct |
37 ms |
88004 KB |
Output is correct |
19 |
Correct |
43 ms |
88000 KB |
Output is correct |
20 |
Correct |
78 ms |
88212 KB |
Output is correct |
21 |
Correct |
237 ms |
88512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
79748 KB |
Output is correct |
2 |
Correct |
31 ms |
79964 KB |
Output is correct |
3 |
Correct |
108 ms |
79964 KB |
Output is correct |
4 |
Correct |
198 ms |
80216 KB |
Output is correct |
5 |
Correct |
17 ms |
80472 KB |
Output is correct |
6 |
Correct |
37 ms |
80724 KB |
Output is correct |
7 |
Correct |
121 ms |
80760 KB |
Output is correct |
8 |
Correct |
240 ms |
81320 KB |
Output is correct |
9 |
Correct |
31 ms |
84048 KB |
Output is correct |
10 |
Correct |
51 ms |
83928 KB |
Output is correct |
11 |
Correct |
144 ms |
84212 KB |
Output is correct |
12 |
Correct |
274 ms |
84764 KB |
Output is correct |
13 |
Correct |
49 ms |
88660 KB |
Output is correct |
14 |
Correct |
82 ms |
88912 KB |
Output is correct |
15 |
Correct |
170 ms |
89168 KB |
Output is correct |
16 |
Correct |
293 ms |
89264 KB |
Output is correct |
17 |
Correct |
255 ms |
89440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
351 ms |
90136 KB |
Output is correct |
2 |
Correct |
317 ms |
90192 KB |
Output is correct |
3 |
Correct |
329 ms |
90212 KB |
Output is correct |
4 |
Correct |
323 ms |
90196 KB |
Output is correct |
5 |
Correct |
371 ms |
89848 KB |
Output is correct |
6 |
Correct |
305 ms |
89796 KB |
Output is correct |
7 |
Correct |
335 ms |
93524 KB |
Output is correct |
8 |
Correct |
330 ms |
93268 KB |
Output is correct |
9 |
Correct |
336 ms |
93060 KB |
Output is correct |
10 |
Correct |
335 ms |
93012 KB |
Output is correct |
11 |
Correct |
339 ms |
92928 KB |
Output is correct |
12 |
Correct |
352 ms |
91900 KB |
Output is correct |
13 |
Correct |
389 ms |
98108 KB |
Output is correct |
14 |
Correct |
357 ms |
97892 KB |
Output is correct |
15 |
Correct |
395 ms |
98172 KB |
Output is correct |
16 |
Correct |
379 ms |
97872 KB |
Output is correct |
17 |
Correct |
374 ms |
97124 KB |
Output is correct |
18 |
Correct |
355 ms |
93636 KB |
Output is correct |
19 |
Correct |
355 ms |
97812 KB |
Output is correct |
20 |
Correct |
353 ms |
97888 KB |
Output is correct |
21 |
Correct |
375 ms |
97908 KB |
Output is correct |
22 |
Correct |
366 ms |
98308 KB |
Output is correct |
23 |
Correct |
363 ms |
96972 KB |
Output is correct |
24 |
Correct |
355 ms |
93624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
79708 KB |
Output is correct |
2 |
Correct |
12 ms |
79708 KB |
Output is correct |
3 |
Correct |
11 ms |
79708 KB |
Output is correct |
4 |
Correct |
12 ms |
79960 KB |
Output is correct |
5 |
Correct |
11 ms |
79684 KB |
Output is correct |
6 |
Correct |
11 ms |
79668 KB |
Output is correct |
7 |
Correct |
12 ms |
79708 KB |
Output is correct |
8 |
Correct |
11 ms |
79708 KB |
Output is correct |
9 |
Correct |
11 ms |
79708 KB |
Output is correct |
10 |
Correct |
12 ms |
79708 KB |
Output is correct |
11 |
Correct |
12 ms |
79708 KB |
Output is correct |
12 |
Correct |
11 ms |
79708 KB |
Output is correct |
13 |
Correct |
11 ms |
79708 KB |
Output is correct |
14 |
Correct |
12 ms |
79660 KB |
Output is correct |
15 |
Correct |
12 ms |
79708 KB |
Output is correct |
16 |
Correct |
12 ms |
79648 KB |
Output is correct |
17 |
Correct |
11 ms |
79708 KB |
Output is correct |
18 |
Correct |
12 ms |
79660 KB |
Output is correct |
19 |
Correct |
21 ms |
79704 KB |
Output is correct |
20 |
Correct |
21 ms |
79708 KB |
Output is correct |
21 |
Correct |
23 ms |
79708 KB |
Output is correct |
22 |
Correct |
21 ms |
79964 KB |
Output is correct |
23 |
Correct |
23 ms |
80220 KB |
Output is correct |
24 |
Correct |
28 ms |
80260 KB |
Output is correct |
25 |
Correct |
24 ms |
80220 KB |
Output is correct |
26 |
Correct |
25 ms |
80640 KB |
Output is correct |
27 |
Correct |
11 ms |
79708 KB |
Output is correct |
28 |
Correct |
12 ms |
79720 KB |
Output is correct |
29 |
Correct |
15 ms |
79704 KB |
Output is correct |
30 |
Correct |
40 ms |
79708 KB |
Output is correct |
31 |
Correct |
153 ms |
80184 KB |
Output is correct |
32 |
Correct |
11 ms |
79704 KB |
Output is correct |
33 |
Correct |
12 ms |
79708 KB |
Output is correct |
34 |
Correct |
13 ms |
79904 KB |
Output is correct |
35 |
Correct |
15 ms |
79708 KB |
Output is correct |
36 |
Correct |
45 ms |
79956 KB |
Output is correct |
37 |
Correct |
165 ms |
80136 KB |
Output is correct |
38 |
Correct |
13 ms |
80216 KB |
Output is correct |
39 |
Correct |
14 ms |
80220 KB |
Output is correct |
40 |
Correct |
16 ms |
80524 KB |
Output is correct |
41 |
Correct |
46 ms |
80216 KB |
Output is correct |
42 |
Correct |
182 ms |
80588 KB |
Output is correct |
43 |
Correct |
39 ms |
88000 KB |
Output is correct |
44 |
Correct |
37 ms |
88004 KB |
Output is correct |
45 |
Correct |
43 ms |
88000 KB |
Output is correct |
46 |
Correct |
78 ms |
88212 KB |
Output is correct |
47 |
Correct |
237 ms |
88512 KB |
Output is correct |
48 |
Correct |
14 ms |
79748 KB |
Output is correct |
49 |
Correct |
31 ms |
79964 KB |
Output is correct |
50 |
Correct |
108 ms |
79964 KB |
Output is correct |
51 |
Correct |
198 ms |
80216 KB |
Output is correct |
52 |
Correct |
17 ms |
80472 KB |
Output is correct |
53 |
Correct |
37 ms |
80724 KB |
Output is correct |
54 |
Correct |
121 ms |
80760 KB |
Output is correct |
55 |
Correct |
240 ms |
81320 KB |
Output is correct |
56 |
Correct |
31 ms |
84048 KB |
Output is correct |
57 |
Correct |
51 ms |
83928 KB |
Output is correct |
58 |
Correct |
144 ms |
84212 KB |
Output is correct |
59 |
Correct |
274 ms |
84764 KB |
Output is correct |
60 |
Correct |
49 ms |
88660 KB |
Output is correct |
61 |
Correct |
82 ms |
88912 KB |
Output is correct |
62 |
Correct |
170 ms |
89168 KB |
Output is correct |
63 |
Correct |
293 ms |
89264 KB |
Output is correct |
64 |
Correct |
255 ms |
89440 KB |
Output is correct |
65 |
Correct |
351 ms |
90136 KB |
Output is correct |
66 |
Correct |
317 ms |
90192 KB |
Output is correct |
67 |
Correct |
329 ms |
90212 KB |
Output is correct |
68 |
Correct |
323 ms |
90196 KB |
Output is correct |
69 |
Correct |
371 ms |
89848 KB |
Output is correct |
70 |
Correct |
305 ms |
89796 KB |
Output is correct |
71 |
Correct |
335 ms |
93524 KB |
Output is correct |
72 |
Correct |
330 ms |
93268 KB |
Output is correct |
73 |
Correct |
336 ms |
93060 KB |
Output is correct |
74 |
Correct |
335 ms |
93012 KB |
Output is correct |
75 |
Correct |
339 ms |
92928 KB |
Output is correct |
76 |
Correct |
352 ms |
91900 KB |
Output is correct |
77 |
Correct |
389 ms |
98108 KB |
Output is correct |
78 |
Correct |
357 ms |
97892 KB |
Output is correct |
79 |
Correct |
395 ms |
98172 KB |
Output is correct |
80 |
Correct |
379 ms |
97872 KB |
Output is correct |
81 |
Correct |
374 ms |
97124 KB |
Output is correct |
82 |
Correct |
355 ms |
93636 KB |
Output is correct |
83 |
Correct |
355 ms |
97812 KB |
Output is correct |
84 |
Correct |
353 ms |
97888 KB |
Output is correct |
85 |
Correct |
375 ms |
97908 KB |
Output is correct |
86 |
Correct |
366 ms |
98308 KB |
Output is correct |
87 |
Correct |
363 ms |
96972 KB |
Output is correct |
88 |
Correct |
355 ms |
93624 KB |
Output is correct |
89 |
Correct |
316 ms |
89884 KB |
Output is correct |
90 |
Correct |
317 ms |
90444 KB |
Output is correct |
91 |
Correct |
312 ms |
91652 KB |
Output is correct |
92 |
Correct |
341 ms |
91984 KB |
Output is correct |
93 |
Correct |
344 ms |
94876 KB |
Output is correct |
94 |
Correct |
372 ms |
93700 KB |
Output is correct |
95 |
Correct |
351 ms |
95316 KB |
Output is correct |
96 |
Correct |
371 ms |
94192 KB |
Output is correct |
97 |
Correct |
349 ms |
95308 KB |
Output is correct |
98 |
Correct |
372 ms |
97868 KB |
Output is correct |
99 |
Correct |
354 ms |
95316 KB |
Output is correct |
100 |
Correct |
352 ms |
95140 KB |
Output is correct |