#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{
LL maxDepth = -INF, minDepth = INF;
LL leftMax = -INF, rightMax = -INF;
LL diameter = 0;
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 += val;
segt[idx].minDepth += val;
segt[idx].leftMax -= val;
segt[idx].rightMax -= 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 - 2 * r.minDepth);
head.rightMax = max(l.rightMax, r.rightMax);
head.rightMax = max(head.rightMax, r.maxDepth - 2 * l.minDepth);
head.diameter = max(l.diameter, r.diameter);
head.diameter = max(head.diameter, l.maxDepth + r.rightMax);
head.diameter = max(head.diameter, r.maxDepth + l.leftMax);
//~ 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]];
segt[idx].leftMax = segt[idx].rightMax = -depth[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;
pushDown();
ans = segt[1].diameter;
cout << ans << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42076 KB |
Output is correct |
2 |
Correct |
6 ms |
42076 KB |
Output is correct |
3 |
Correct |
6 ms |
42184 KB |
Output is correct |
4 |
Correct |
6 ms |
42188 KB |
Output is correct |
5 |
Correct |
6 ms |
42076 KB |
Output is correct |
6 |
Correct |
7 ms |
42076 KB |
Output is correct |
7 |
Correct |
6 ms |
42076 KB |
Output is correct |
8 |
Correct |
6 ms |
42072 KB |
Output is correct |
9 |
Correct |
6 ms |
42076 KB |
Output is correct |
10 |
Correct |
6 ms |
42076 KB |
Output is correct |
11 |
Correct |
6 ms |
42148 KB |
Output is correct |
12 |
Correct |
6 ms |
42072 KB |
Output is correct |
13 |
Correct |
6 ms |
42076 KB |
Output is correct |
14 |
Correct |
6 ms |
42076 KB |
Output is correct |
15 |
Correct |
7 ms |
42196 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42248 KB |
Output is correct |
18 |
Correct |
6 ms |
42076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42076 KB |
Output is correct |
2 |
Correct |
6 ms |
42076 KB |
Output is correct |
3 |
Correct |
6 ms |
42184 KB |
Output is correct |
4 |
Correct |
6 ms |
42188 KB |
Output is correct |
5 |
Correct |
6 ms |
42076 KB |
Output is correct |
6 |
Correct |
7 ms |
42076 KB |
Output is correct |
7 |
Correct |
6 ms |
42076 KB |
Output is correct |
8 |
Correct |
6 ms |
42072 KB |
Output is correct |
9 |
Correct |
6 ms |
42076 KB |
Output is correct |
10 |
Correct |
6 ms |
42076 KB |
Output is correct |
11 |
Correct |
6 ms |
42148 KB |
Output is correct |
12 |
Correct |
6 ms |
42072 KB |
Output is correct |
13 |
Correct |
6 ms |
42076 KB |
Output is correct |
14 |
Correct |
6 ms |
42076 KB |
Output is correct |
15 |
Correct |
7 ms |
42196 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42248 KB |
Output is correct |
18 |
Correct |
6 ms |
42076 KB |
Output is correct |
19 |
Correct |
14 ms |
42332 KB |
Output is correct |
20 |
Correct |
14 ms |
42332 KB |
Output is correct |
21 |
Correct |
15 ms |
42332 KB |
Output is correct |
22 |
Correct |
16 ms |
42432 KB |
Output is correct |
23 |
Correct |
19 ms |
42584 KB |
Output is correct |
24 |
Correct |
17 ms |
42588 KB |
Output is correct |
25 |
Correct |
16 ms |
42772 KB |
Output is correct |
26 |
Correct |
24 ms |
43116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
7 ms |
42072 KB |
Output is correct |
3 |
Correct |
9 ms |
42072 KB |
Output is correct |
4 |
Correct |
32 ms |
42076 KB |
Output is correct |
5 |
Correct |
148 ms |
42640 KB |
Output is correct |
6 |
Correct |
6 ms |
42072 KB |
Output is correct |
7 |
Correct |
6 ms |
42160 KB |
Output is correct |
8 |
Correct |
6 ms |
42076 KB |
Output is correct |
9 |
Correct |
9 ms |
42076 KB |
Output is correct |
10 |
Correct |
34 ms |
42348 KB |
Output is correct |
11 |
Correct |
146 ms |
42536 KB |
Output is correct |
12 |
Correct |
7 ms |
42584 KB |
Output is correct |
13 |
Correct |
9 ms |
42588 KB |
Output is correct |
14 |
Correct |
11 ms |
42588 KB |
Output is correct |
15 |
Correct |
37 ms |
42656 KB |
Output is correct |
16 |
Correct |
160 ms |
43192 KB |
Output is correct |
17 |
Correct |
30 ms |
50372 KB |
Output is correct |
18 |
Correct |
32 ms |
50376 KB |
Output is correct |
19 |
Correct |
35 ms |
50368 KB |
Output is correct |
20 |
Correct |
67 ms |
50636 KB |
Output is correct |
21 |
Correct |
218 ms |
51092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
42328 KB |
Output is correct |
2 |
Correct |
22 ms |
42332 KB |
Output is correct |
3 |
Correct |
88 ms |
42580 KB |
Output is correct |
4 |
Correct |
161 ms |
42712 KB |
Output is correct |
5 |
Correct |
11 ms |
43100 KB |
Output is correct |
6 |
Correct |
26 ms |
43204 KB |
Output is correct |
7 |
Correct |
92 ms |
43352 KB |
Output is correct |
8 |
Correct |
175 ms |
43552 KB |
Output is correct |
9 |
Correct |
22 ms |
46936 KB |
Output is correct |
10 |
Correct |
38 ms |
46928 KB |
Output is correct |
11 |
Correct |
114 ms |
47184 KB |
Output is correct |
12 |
Correct |
201 ms |
47420 KB |
Output is correct |
13 |
Correct |
37 ms |
51300 KB |
Output is correct |
14 |
Correct |
54 ms |
51288 KB |
Output is correct |
15 |
Correct |
131 ms |
51536 KB |
Output is correct |
16 |
Correct |
224 ms |
51792 KB |
Output is correct |
17 |
Correct |
230 ms |
51856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
56656 KB |
Output is correct |
2 |
Correct |
259 ms |
56660 KB |
Output is correct |
3 |
Correct |
266 ms |
56684 KB |
Output is correct |
4 |
Correct |
251 ms |
56576 KB |
Output is correct |
5 |
Correct |
263 ms |
56528 KB |
Output is correct |
6 |
Correct |
237 ms |
56300 KB |
Output is correct |
7 |
Correct |
318 ms |
59828 KB |
Output is correct |
8 |
Correct |
269 ms |
59736 KB |
Output is correct |
9 |
Correct |
294 ms |
59752 KB |
Output is correct |
10 |
Correct |
270 ms |
59728 KB |
Output is correct |
11 |
Correct |
270 ms |
59436 KB |
Output is correct |
12 |
Correct |
283 ms |
58564 KB |
Output is correct |
13 |
Correct |
347 ms |
64340 KB |
Output is correct |
14 |
Correct |
309 ms |
64340 KB |
Output is correct |
15 |
Correct |
327 ms |
64388 KB |
Output is correct |
16 |
Correct |
311 ms |
64472 KB |
Output is correct |
17 |
Correct |
304 ms |
63556 KB |
Output is correct |
18 |
Correct |
280 ms |
60296 KB |
Output is correct |
19 |
Correct |
309 ms |
64284 KB |
Output is correct |
20 |
Correct |
327 ms |
64528 KB |
Output is correct |
21 |
Correct |
317 ms |
64336 KB |
Output is correct |
22 |
Correct |
319 ms |
64396 KB |
Output is correct |
23 |
Correct |
305 ms |
63532 KB |
Output is correct |
24 |
Correct |
280 ms |
60248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42076 KB |
Output is correct |
2 |
Correct |
6 ms |
42076 KB |
Output is correct |
3 |
Correct |
6 ms |
42184 KB |
Output is correct |
4 |
Correct |
6 ms |
42188 KB |
Output is correct |
5 |
Correct |
6 ms |
42076 KB |
Output is correct |
6 |
Correct |
7 ms |
42076 KB |
Output is correct |
7 |
Correct |
6 ms |
42076 KB |
Output is correct |
8 |
Correct |
6 ms |
42072 KB |
Output is correct |
9 |
Correct |
6 ms |
42076 KB |
Output is correct |
10 |
Correct |
6 ms |
42076 KB |
Output is correct |
11 |
Correct |
6 ms |
42148 KB |
Output is correct |
12 |
Correct |
6 ms |
42072 KB |
Output is correct |
13 |
Correct |
6 ms |
42076 KB |
Output is correct |
14 |
Correct |
6 ms |
42076 KB |
Output is correct |
15 |
Correct |
7 ms |
42196 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42248 KB |
Output is correct |
18 |
Correct |
6 ms |
42076 KB |
Output is correct |
19 |
Correct |
14 ms |
42332 KB |
Output is correct |
20 |
Correct |
14 ms |
42332 KB |
Output is correct |
21 |
Correct |
15 ms |
42332 KB |
Output is correct |
22 |
Correct |
16 ms |
42432 KB |
Output is correct |
23 |
Correct |
19 ms |
42584 KB |
Output is correct |
24 |
Correct |
17 ms |
42588 KB |
Output is correct |
25 |
Correct |
16 ms |
42772 KB |
Output is correct |
26 |
Correct |
24 ms |
43116 KB |
Output is correct |
27 |
Correct |
6 ms |
42072 KB |
Output is correct |
28 |
Correct |
7 ms |
42072 KB |
Output is correct |
29 |
Correct |
9 ms |
42072 KB |
Output is correct |
30 |
Correct |
32 ms |
42076 KB |
Output is correct |
31 |
Correct |
148 ms |
42640 KB |
Output is correct |
32 |
Correct |
6 ms |
42072 KB |
Output is correct |
33 |
Correct |
6 ms |
42160 KB |
Output is correct |
34 |
Correct |
6 ms |
42076 KB |
Output is correct |
35 |
Correct |
9 ms |
42076 KB |
Output is correct |
36 |
Correct |
34 ms |
42348 KB |
Output is correct |
37 |
Correct |
146 ms |
42536 KB |
Output is correct |
38 |
Correct |
7 ms |
42584 KB |
Output is correct |
39 |
Correct |
9 ms |
42588 KB |
Output is correct |
40 |
Correct |
11 ms |
42588 KB |
Output is correct |
41 |
Correct |
37 ms |
42656 KB |
Output is correct |
42 |
Correct |
160 ms |
43192 KB |
Output is correct |
43 |
Correct |
30 ms |
50372 KB |
Output is correct |
44 |
Correct |
32 ms |
50376 KB |
Output is correct |
45 |
Correct |
35 ms |
50368 KB |
Output is correct |
46 |
Correct |
67 ms |
50636 KB |
Output is correct |
47 |
Correct |
218 ms |
51092 KB |
Output is correct |
48 |
Correct |
8 ms |
42328 KB |
Output is correct |
49 |
Correct |
22 ms |
42332 KB |
Output is correct |
50 |
Correct |
88 ms |
42580 KB |
Output is correct |
51 |
Correct |
161 ms |
42712 KB |
Output is correct |
52 |
Correct |
11 ms |
43100 KB |
Output is correct |
53 |
Correct |
26 ms |
43204 KB |
Output is correct |
54 |
Correct |
92 ms |
43352 KB |
Output is correct |
55 |
Correct |
175 ms |
43552 KB |
Output is correct |
56 |
Correct |
22 ms |
46936 KB |
Output is correct |
57 |
Correct |
38 ms |
46928 KB |
Output is correct |
58 |
Correct |
114 ms |
47184 KB |
Output is correct |
59 |
Correct |
201 ms |
47420 KB |
Output is correct |
60 |
Correct |
37 ms |
51300 KB |
Output is correct |
61 |
Correct |
54 ms |
51288 KB |
Output is correct |
62 |
Correct |
131 ms |
51536 KB |
Output is correct |
63 |
Correct |
224 ms |
51792 KB |
Output is correct |
64 |
Correct |
230 ms |
51856 KB |
Output is correct |
65 |
Correct |
252 ms |
56656 KB |
Output is correct |
66 |
Correct |
259 ms |
56660 KB |
Output is correct |
67 |
Correct |
266 ms |
56684 KB |
Output is correct |
68 |
Correct |
251 ms |
56576 KB |
Output is correct |
69 |
Correct |
263 ms |
56528 KB |
Output is correct |
70 |
Correct |
237 ms |
56300 KB |
Output is correct |
71 |
Correct |
318 ms |
59828 KB |
Output is correct |
72 |
Correct |
269 ms |
59736 KB |
Output is correct |
73 |
Correct |
294 ms |
59752 KB |
Output is correct |
74 |
Correct |
270 ms |
59728 KB |
Output is correct |
75 |
Correct |
270 ms |
59436 KB |
Output is correct |
76 |
Correct |
283 ms |
58564 KB |
Output is correct |
77 |
Correct |
347 ms |
64340 KB |
Output is correct |
78 |
Correct |
309 ms |
64340 KB |
Output is correct |
79 |
Correct |
327 ms |
64388 KB |
Output is correct |
80 |
Correct |
311 ms |
64472 KB |
Output is correct |
81 |
Correct |
304 ms |
63556 KB |
Output is correct |
82 |
Correct |
280 ms |
60296 KB |
Output is correct |
83 |
Correct |
309 ms |
64284 KB |
Output is correct |
84 |
Correct |
327 ms |
64528 KB |
Output is correct |
85 |
Correct |
317 ms |
64336 KB |
Output is correct |
86 |
Correct |
319 ms |
64396 KB |
Output is correct |
87 |
Correct |
305 ms |
63532 KB |
Output is correct |
88 |
Correct |
280 ms |
60248 KB |
Output is correct |
89 |
Correct |
286 ms |
55628 KB |
Output is correct |
90 |
Correct |
269 ms |
56132 KB |
Output is correct |
91 |
Correct |
255 ms |
57680 KB |
Output is correct |
92 |
Correct |
273 ms |
57684 KB |
Output is correct |
93 |
Correct |
273 ms |
60392 KB |
Output is correct |
94 |
Correct |
290 ms |
59596 KB |
Output is correct |
95 |
Correct |
295 ms |
61388 KB |
Output is correct |
96 |
Correct |
296 ms |
60092 KB |
Output is correct |
97 |
Correct |
295 ms |
61320 KB |
Output is correct |
98 |
Correct |
330 ms |
63616 KB |
Output is correct |
99 |
Correct |
299 ms |
61052 KB |
Output is correct |
100 |
Correct |
293 ms |
61012 KB |
Output is correct |