#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100'000 + 10;
int n, q, maxW;
vector<pair<int, int>> ad[N];
struct Edge {
int u, v, w;
friend istream& operator >> (istream& is, auto& rhs) {
return is >> rhs.u >> rhs.v >> rhs.w;
}
} edge[N];
int sz[N], par[N];
void dfs1(int u, int p = -1) {
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
par[v] = u;
dfs1(v, u);
sz[u] += sz[v] + 1;
}
}
int head[N], st[N], ed[N], rvs[N], it;
void hld(int u, int p = -1) {
if (!head[u]) head[u] = u;
st[u] = ++it; rvs[it] = u;
sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) {
return sz[a.first] > sz[b.first];
});
bool heavy = false;
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
if (!heavy) head[v] = head[u], hld(v, u);
else hld(v, u);
heavy = true;
}
ed[u] = it;
}
struct IT {
int f[N << 2], lazy[N << 2];
void push(int s) {
f[s << 1] += lazy[s]; f[s << 1 | 1] += lazy[s];
lazy[s << 1] += lazy[s]; lazy[s << 1 | 1] += lazy[s];
lazy[s] = 0;
}
void update(int s, int l, int r, int u, int v, int x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
f[s] += x;
lazy[s] += x;
return;
}
push(s);
int mid = l + r >> 1;
update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
f[s] = max(f[s << 1], f[s << 1 | 1]);
}
void assign(int s, int l, int r, int i, int x) {
if (i < l || i > r) return;
if (l == r) {
f[s] = x;
lazy[s] = 0;
return;
}
push(s);
int mid = l + r >> 1;
assign(s << 1, l, mid, i, x); assign(s << 1 | 1, mid + 1, r, i, x);
f[s] = max(f[s << 1], f[s << 1 | 1]);
}
int query(int s, int l, int r, int u, int v) {
if (v < l || u > r) return -20'000'000'000'000'000;
if (u <= l && r <= v) return f[s];
push(s);
int mid = l + r >> 1;
return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}
int lower_bound(int s, int l, int r, int x) {
if (l == r) return l;
push(s);
int mid = l + r >> 1;
if (f[s << 1] >= x) return lower_bound(s << 1, l, mid, x);
return lower_bound(s << 1 | 1, mid + 1, r, x);
}
} D, T;
void dfs2(int u, int p = -1) {
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
D.update(1, 1, n, st[v], ed[v], w);
dfs2(v, u);
}
T.update(1, 1, n, st[u], st[u], -2 * D.query(1, 1, n, st[u], st[u]));
int heavy = (ad[u].size() - (u != 1) <= 1 ? 0 : ad[u][u != 1].first);
if (!heavy) return;
T.update(1, 1, n, st[u], st[u], D.query(1, 1, n, ed[heavy] + 1, ed[u]));
}
void update(int i, int nW) {
auto [u, v, w] = edge[i];
edge[i].w = nW;
if (st[u] > st[v] ) swap(u, v);
D.update(1, 1, n, st[v], ed[v], nW - w);
T.update(1, 1, n, st[v], ed[v], w - nW);
while (u) {
T.assign(1, 1, n, st[u], 0);
T.update(1, 1, n, st[u], st[u], -2 * D.query(1, 1, n, st[u], st[u]));
int heavy = (ad[u].size() - (u != 1) <= 1 ? 0 : ad[u][u != 1].first);
if (heavy)
T.update(1, 1, n, st[u], st[u], D.query(1, 1, n, ed[heavy] + 1, ed[u]));
if (u == 1) break;
u = par[head[u]];
}
}
int get() {
int d = D.f[1],
u = rvs[D.lower_bound(1, 1, n, d)],
ret = 0;
while (u) {
int minus = 2 * D.query(1, 1, n, st[par[head[u]]], st[par[head[u]]]);
ret = max(ret, T.query(1, 1, n, st[head[u]], st[u] - 1));
ret = max(ret, D.query(1, 1, n, st[par[head[u]]], st[head[u]] - 1) - minus);
ret = max(ret, D.query(1, 1, n, ed[head[u]] + 1, ed[par[head[u]]]) - minus);
if (u == 1) break;
u = par[head[u]];
}
return ret + d;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q >> maxW;
for (int i = 0; i < n - 1; ++i) {
cin >> edge[i];
const auto& [u, v, w] = edge[i];
ad[u].push_back({v, w});
ad[v].push_back({u, w});
}
dfs1(par[1] = 1); hld(1);
dfs2(1);
int siesta = 0;
while (q--) {
int i, nW; cin >> i >> nW;
i = (i + siesta) % (n - 1);
nW = (nW + siesta) % maxW;
update(i, nW);
cout << (siesta = get()) << "\n";
}
}
Compilation message
diameter.cpp:13:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
13 | friend istream& operator >> (istream& is, auto& rhs) {
| ^~~~
diameter.cpp: In member function 'void IT::update(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In member function 'void IT::assign(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In member function 'long long int IT::query(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In member function 'long long int IT::lower_bound(long long int, long long int, long long int, long long int)':
diameter.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7768 KB |
Output is correct |
2 |
Correct |
2 ms |
7768 KB |
Output is correct |
3 |
Correct |
2 ms |
7772 KB |
Output is correct |
4 |
Correct |
2 ms |
7772 KB |
Output is correct |
5 |
Correct |
2 ms |
7772 KB |
Output is correct |
6 |
Correct |
2 ms |
7772 KB |
Output is correct |
7 |
Correct |
2 ms |
7772 KB |
Output is correct |
8 |
Correct |
2 ms |
7772 KB |
Output is correct |
9 |
Correct |
2 ms |
7772 KB |
Output is correct |
10 |
Correct |
2 ms |
7772 KB |
Output is correct |
11 |
Correct |
2 ms |
7772 KB |
Output is correct |
12 |
Correct |
2 ms |
7772 KB |
Output is correct |
13 |
Correct |
2 ms |
7772 KB |
Output is correct |
14 |
Correct |
2 ms |
7772 KB |
Output is correct |
15 |
Correct |
2 ms |
7772 KB |
Output is correct |
16 |
Correct |
2 ms |
7772 KB |
Output is correct |
17 |
Correct |
2 ms |
7772 KB |
Output is correct |
18 |
Correct |
2 ms |
7772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7768 KB |
Output is correct |
2 |
Correct |
2 ms |
7768 KB |
Output is correct |
3 |
Correct |
2 ms |
7772 KB |
Output is correct |
4 |
Correct |
2 ms |
7772 KB |
Output is correct |
5 |
Correct |
2 ms |
7772 KB |
Output is correct |
6 |
Correct |
2 ms |
7772 KB |
Output is correct |
7 |
Correct |
2 ms |
7772 KB |
Output is correct |
8 |
Correct |
2 ms |
7772 KB |
Output is correct |
9 |
Correct |
2 ms |
7772 KB |
Output is correct |
10 |
Correct |
2 ms |
7772 KB |
Output is correct |
11 |
Correct |
2 ms |
7772 KB |
Output is correct |
12 |
Correct |
2 ms |
7772 KB |
Output is correct |
13 |
Correct |
2 ms |
7772 KB |
Output is correct |
14 |
Correct |
2 ms |
7772 KB |
Output is correct |
15 |
Correct |
2 ms |
7772 KB |
Output is correct |
16 |
Correct |
2 ms |
7772 KB |
Output is correct |
17 |
Correct |
2 ms |
7772 KB |
Output is correct |
18 |
Correct |
2 ms |
7772 KB |
Output is correct |
19 |
Correct |
14 ms |
8024 KB |
Output is correct |
20 |
Correct |
13 ms |
8028 KB |
Output is correct |
21 |
Correct |
11 ms |
8028 KB |
Output is correct |
22 |
Correct |
8 ms |
8244 KB |
Output is correct |
23 |
Correct |
23 ms |
10844 KB |
Output is correct |
24 |
Correct |
21 ms |
10840 KB |
Output is correct |
25 |
Correct |
17 ms |
10844 KB |
Output is correct |
26 |
Correct |
13 ms |
11612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7772 KB |
Output is correct |
2 |
Correct |
2 ms |
7772 KB |
Output is correct |
3 |
Correct |
3 ms |
7768 KB |
Output is correct |
4 |
Correct |
12 ms |
8112 KB |
Output is correct |
5 |
Correct |
54 ms |
8944 KB |
Output is correct |
6 |
Correct |
2 ms |
7772 KB |
Output is correct |
7 |
Correct |
2 ms |
7772 KB |
Output is correct |
8 |
Correct |
2 ms |
7772 KB |
Output is correct |
9 |
Correct |
4 ms |
7772 KB |
Output is correct |
10 |
Correct |
20 ms |
8204 KB |
Output is correct |
11 |
Correct |
86 ms |
9044 KB |
Output is correct |
12 |
Correct |
5 ms |
10840 KB |
Output is correct |
13 |
Correct |
5 ms |
10764 KB |
Output is correct |
14 |
Correct |
7 ms |
10788 KB |
Output is correct |
15 |
Correct |
28 ms |
11352 KB |
Output is correct |
16 |
Correct |
125 ms |
12196 KB |
Output is correct |
17 |
Correct |
67 ms |
25044 KB |
Output is correct |
18 |
Correct |
64 ms |
25120 KB |
Output is correct |
19 |
Correct |
69 ms |
25188 KB |
Output is correct |
20 |
Correct |
112 ms |
25284 KB |
Output is correct |
21 |
Correct |
277 ms |
26812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8028 KB |
Output is correct |
2 |
Correct |
28 ms |
8156 KB |
Output is correct |
3 |
Correct |
131 ms |
8744 KB |
Output is correct |
4 |
Correct |
248 ms |
9292 KB |
Output is correct |
5 |
Correct |
14 ms |
13892 KB |
Output is correct |
6 |
Correct |
55 ms |
13660 KB |
Output is correct |
7 |
Correct |
231 ms |
14164 KB |
Output is correct |
8 |
Correct |
464 ms |
15404 KB |
Output is correct |
9 |
Correct |
48 ms |
20820 KB |
Output is correct |
10 |
Correct |
111 ms |
21108 KB |
Output is correct |
11 |
Correct |
367 ms |
21844 KB |
Output is correct |
12 |
Correct |
757 ms |
22612 KB |
Output is correct |
13 |
Correct |
89 ms |
26196 KB |
Output is correct |
14 |
Correct |
161 ms |
26324 KB |
Output is correct |
15 |
Correct |
473 ms |
26912 KB |
Output is correct |
16 |
Correct |
847 ms |
27980 KB |
Output is correct |
17 |
Correct |
1202 ms |
27784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
695 ms |
30096 KB |
Output is correct |
2 |
Correct |
794 ms |
30240 KB |
Output is correct |
3 |
Correct |
749 ms |
30328 KB |
Output is correct |
4 |
Correct |
747 ms |
30192 KB |
Output is correct |
5 |
Correct |
710 ms |
29904 KB |
Output is correct |
6 |
Correct |
737 ms |
29936 KB |
Output is correct |
7 |
Correct |
485 ms |
36028 KB |
Output is correct |
8 |
Correct |
511 ms |
36180 KB |
Output is correct |
9 |
Correct |
489 ms |
36168 KB |
Output is correct |
10 |
Correct |
518 ms |
36032 KB |
Output is correct |
11 |
Correct |
481 ms |
35724 KB |
Output is correct |
12 |
Correct |
389 ms |
34124 KB |
Output is correct |
13 |
Correct |
342 ms |
45908 KB |
Output is correct |
14 |
Correct |
419 ms |
45648 KB |
Output is correct |
15 |
Correct |
411 ms |
45792 KB |
Output is correct |
16 |
Correct |
370 ms |
45412 KB |
Output is correct |
17 |
Correct |
414 ms |
44212 KB |
Output is correct |
18 |
Correct |
350 ms |
37440 KB |
Output is correct |
19 |
Correct |
323 ms |
45620 KB |
Output is correct |
20 |
Correct |
392 ms |
45468 KB |
Output is correct |
21 |
Correct |
383 ms |
45788 KB |
Output is correct |
22 |
Correct |
371 ms |
45508 KB |
Output is correct |
23 |
Correct |
359 ms |
43984 KB |
Output is correct |
24 |
Correct |
399 ms |
37472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7768 KB |
Output is correct |
2 |
Correct |
2 ms |
7768 KB |
Output is correct |
3 |
Correct |
2 ms |
7772 KB |
Output is correct |
4 |
Correct |
2 ms |
7772 KB |
Output is correct |
5 |
Correct |
2 ms |
7772 KB |
Output is correct |
6 |
Correct |
2 ms |
7772 KB |
Output is correct |
7 |
Correct |
2 ms |
7772 KB |
Output is correct |
8 |
Correct |
2 ms |
7772 KB |
Output is correct |
9 |
Correct |
2 ms |
7772 KB |
Output is correct |
10 |
Correct |
2 ms |
7772 KB |
Output is correct |
11 |
Correct |
2 ms |
7772 KB |
Output is correct |
12 |
Correct |
2 ms |
7772 KB |
Output is correct |
13 |
Correct |
2 ms |
7772 KB |
Output is correct |
14 |
Correct |
2 ms |
7772 KB |
Output is correct |
15 |
Correct |
2 ms |
7772 KB |
Output is correct |
16 |
Correct |
2 ms |
7772 KB |
Output is correct |
17 |
Correct |
2 ms |
7772 KB |
Output is correct |
18 |
Correct |
2 ms |
7772 KB |
Output is correct |
19 |
Correct |
14 ms |
8024 KB |
Output is correct |
20 |
Correct |
13 ms |
8028 KB |
Output is correct |
21 |
Correct |
11 ms |
8028 KB |
Output is correct |
22 |
Correct |
8 ms |
8244 KB |
Output is correct |
23 |
Correct |
23 ms |
10844 KB |
Output is correct |
24 |
Correct |
21 ms |
10840 KB |
Output is correct |
25 |
Correct |
17 ms |
10844 KB |
Output is correct |
26 |
Correct |
13 ms |
11612 KB |
Output is correct |
27 |
Correct |
2 ms |
7772 KB |
Output is correct |
28 |
Correct |
2 ms |
7772 KB |
Output is correct |
29 |
Correct |
3 ms |
7768 KB |
Output is correct |
30 |
Correct |
12 ms |
8112 KB |
Output is correct |
31 |
Correct |
54 ms |
8944 KB |
Output is correct |
32 |
Correct |
2 ms |
7772 KB |
Output is correct |
33 |
Correct |
2 ms |
7772 KB |
Output is correct |
34 |
Correct |
2 ms |
7772 KB |
Output is correct |
35 |
Correct |
4 ms |
7772 KB |
Output is correct |
36 |
Correct |
20 ms |
8204 KB |
Output is correct |
37 |
Correct |
86 ms |
9044 KB |
Output is correct |
38 |
Correct |
5 ms |
10840 KB |
Output is correct |
39 |
Correct |
5 ms |
10764 KB |
Output is correct |
40 |
Correct |
7 ms |
10788 KB |
Output is correct |
41 |
Correct |
28 ms |
11352 KB |
Output is correct |
42 |
Correct |
125 ms |
12196 KB |
Output is correct |
43 |
Correct |
67 ms |
25044 KB |
Output is correct |
44 |
Correct |
64 ms |
25120 KB |
Output is correct |
45 |
Correct |
69 ms |
25188 KB |
Output is correct |
46 |
Correct |
112 ms |
25284 KB |
Output is correct |
47 |
Correct |
277 ms |
26812 KB |
Output is correct |
48 |
Correct |
5 ms |
8028 KB |
Output is correct |
49 |
Correct |
28 ms |
8156 KB |
Output is correct |
50 |
Correct |
131 ms |
8744 KB |
Output is correct |
51 |
Correct |
248 ms |
9292 KB |
Output is correct |
52 |
Correct |
14 ms |
13892 KB |
Output is correct |
53 |
Correct |
55 ms |
13660 KB |
Output is correct |
54 |
Correct |
231 ms |
14164 KB |
Output is correct |
55 |
Correct |
464 ms |
15404 KB |
Output is correct |
56 |
Correct |
48 ms |
20820 KB |
Output is correct |
57 |
Correct |
111 ms |
21108 KB |
Output is correct |
58 |
Correct |
367 ms |
21844 KB |
Output is correct |
59 |
Correct |
757 ms |
22612 KB |
Output is correct |
60 |
Correct |
89 ms |
26196 KB |
Output is correct |
61 |
Correct |
161 ms |
26324 KB |
Output is correct |
62 |
Correct |
473 ms |
26912 KB |
Output is correct |
63 |
Correct |
847 ms |
27980 KB |
Output is correct |
64 |
Correct |
1202 ms |
27784 KB |
Output is correct |
65 |
Correct |
695 ms |
30096 KB |
Output is correct |
66 |
Correct |
794 ms |
30240 KB |
Output is correct |
67 |
Correct |
749 ms |
30328 KB |
Output is correct |
68 |
Correct |
747 ms |
30192 KB |
Output is correct |
69 |
Correct |
710 ms |
29904 KB |
Output is correct |
70 |
Correct |
737 ms |
29936 KB |
Output is correct |
71 |
Correct |
485 ms |
36028 KB |
Output is correct |
72 |
Correct |
511 ms |
36180 KB |
Output is correct |
73 |
Correct |
489 ms |
36168 KB |
Output is correct |
74 |
Correct |
518 ms |
36032 KB |
Output is correct |
75 |
Correct |
481 ms |
35724 KB |
Output is correct |
76 |
Correct |
389 ms |
34124 KB |
Output is correct |
77 |
Correct |
342 ms |
45908 KB |
Output is correct |
78 |
Correct |
419 ms |
45648 KB |
Output is correct |
79 |
Correct |
411 ms |
45792 KB |
Output is correct |
80 |
Correct |
370 ms |
45412 KB |
Output is correct |
81 |
Correct |
414 ms |
44212 KB |
Output is correct |
82 |
Correct |
350 ms |
37440 KB |
Output is correct |
83 |
Correct |
323 ms |
45620 KB |
Output is correct |
84 |
Correct |
392 ms |
45468 KB |
Output is correct |
85 |
Correct |
383 ms |
45788 KB |
Output is correct |
86 |
Correct |
371 ms |
45508 KB |
Output is correct |
87 |
Correct |
359 ms |
43984 KB |
Output is correct |
88 |
Correct |
399 ms |
37472 KB |
Output is correct |
89 |
Correct |
701 ms |
29128 KB |
Output is correct |
90 |
Correct |
705 ms |
29992 KB |
Output is correct |
91 |
Correct |
485 ms |
32704 KB |
Output is correct |
92 |
Correct |
470 ms |
32708 KB |
Output is correct |
93 |
Correct |
382 ms |
38740 KB |
Output is correct |
94 |
Correct |
414 ms |
36228 KB |
Output is correct |
95 |
Correct |
364 ms |
40220 KB |
Output is correct |
96 |
Correct |
335 ms |
37972 KB |
Output is correct |
97 |
Correct |
363 ms |
40044 KB |
Output is correct |
98 |
Correct |
370 ms |
44888 KB |
Output is correct |
99 |
Correct |
362 ms |
39440 KB |
Output is correct |
100 |
Correct |
342 ms |
39508 KB |
Output is correct |