#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
#define int long long
const int N = 8e5 + 10;
int out[N], in[N], d[N];
vector<int> a;
vector<pair<int, int>> adj[N];
void dfs(int u, int par) {
in[u] = out[u] = sz(a);
a.pb(u);
for(auto x: adj[u]) {
int v = x.first, w = x.second;
if(v == par) continue;
d[v] = d[u] + w;
dfs(v, u);
out[u] = sz(a);
a.pb(u);
}
}
struct node {
int prefix, sufix, ans, max_depth, max_lca;
};
node merge(node a, node b) {
node c;
c.prefix = max({a.prefix, b.prefix, b.max_depth + a.max_lca});
c.sufix = max({a.sufix, b.sufix, a.max_depth + b.max_lca});
c.max_depth = max(a.max_depth, b.max_depth);
c.max_lca = max(a.max_lca, b.max_lca);
c.ans = max({a.ans, b.ans, a.sufix + b.max_depth, a.max_depth + b.prefix});
return c;
}
node t[4 * N];
int lazy[4 * N];
void push(int i, int l, int r) {
if(!lazy[i]) return;
t[i].max_depth += lazy[i];
t[i].max_lca -= 2 * lazy[i];
t[i].prefix -= lazy[i];
t[i].sufix -= lazy[i];
if(l != r) {
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, int val) {
push(i, l, r);
if(l > tr || r < tl) return;
if(l >= tl && r <= tr) {
lazy[i] += val;
push(i, l, r);
return;
}
push(i, l, r);
int mid = l + r >> 1;
modif(2 * i, l, mid, tl, tr, val);
modif(2 * i + 1, mid + 1, r, tl, tr, val);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
const int inf = 1e18;
const node neutral = {-inf, -inf, -inf, -inf, -inf};
void build(int i, int l, int r) {
if(l > r) return;
if(l == r) {
t[i].max_depth = d[a[l]];
t[i].max_lca = -2 * d[a[l]];
t[i].prefix = -inf;
t[i].sufix = -inf;
t[i].ans = -inf;
return;
}
int mid = l + r >> 1;
build(2 * i, l, mid);
build(2 * i + 1, mid + 1, r);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
void solve() {
a.clear();
for(int i = 0; i < 4 * N; ++i) t[i] = neutral;
int n, q, w; cin >> n >> q >> w;
vector<pair<int, int>> edges;
map<pair<int, int>, int> mp;
for(int i = 0; i < n - 1; ++i) {
int u, v, c; cin >> u >> v >> c; --u, --v;
adj[u].pb({v, c});
adj[v].pb({u, c});
edges.pb({u, v});
mp[{u, v}] = mp[{v, u}] = c;
}
dfs(0, -1);
for(int i = 0; i < n - 1; ++i) {
if(in[edges[i].first] > in[edges[i].second]) swap(edges[i].first, edges[i].second);
}
build(1, 0, sz(a) - 1);
int last = 0;
while(q--) {
int d, e; cin >> d >> e; d = (d + last) % (n - 1), e = (e + last) % w;
modif(1, 0, sz(a) - 1, in[edges[d].second], out[edges[d].second], e - mp[{edges[d].first, edges[d].second}]);
last = max(t[1].ans, t[1].max_depth);
mp[{edges[d].first, edges[d].second}] = mp[{edges[d].second, edges[d].first}] = e;
cout << last << "\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
Compilation message
diameter.cpp: In function 'void modif(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid = l + r >> 1;
| ~~^~~
diameter.cpp: In function 'void build(long long int, long long int, long long int)':
diameter.cpp:88:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid = l + r >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
144296 KB |
Output is correct |
2 |
Correct |
59 ms |
144360 KB |
Output is correct |
3 |
Correct |
58 ms |
144312 KB |
Output is correct |
4 |
Correct |
57 ms |
144300 KB |
Output is correct |
5 |
Correct |
60 ms |
144340 KB |
Output is correct |
6 |
Correct |
58 ms |
144276 KB |
Output is correct |
7 |
Correct |
62 ms |
144364 KB |
Output is correct |
8 |
Correct |
56 ms |
144388 KB |
Output is correct |
9 |
Correct |
58 ms |
144268 KB |
Output is correct |
10 |
Correct |
60 ms |
144332 KB |
Output is correct |
11 |
Correct |
60 ms |
144364 KB |
Output is correct |
12 |
Correct |
64 ms |
144332 KB |
Output is correct |
13 |
Correct |
63 ms |
144428 KB |
Output is correct |
14 |
Correct |
58 ms |
144348 KB |
Output is correct |
15 |
Correct |
58 ms |
144284 KB |
Output is correct |
16 |
Correct |
59 ms |
144332 KB |
Output is correct |
17 |
Correct |
59 ms |
144312 KB |
Output is correct |
18 |
Correct |
66 ms |
144388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
144296 KB |
Output is correct |
2 |
Correct |
59 ms |
144360 KB |
Output is correct |
3 |
Correct |
58 ms |
144312 KB |
Output is correct |
4 |
Correct |
57 ms |
144300 KB |
Output is correct |
5 |
Correct |
60 ms |
144340 KB |
Output is correct |
6 |
Correct |
58 ms |
144276 KB |
Output is correct |
7 |
Correct |
62 ms |
144364 KB |
Output is correct |
8 |
Correct |
56 ms |
144388 KB |
Output is correct |
9 |
Correct |
58 ms |
144268 KB |
Output is correct |
10 |
Correct |
60 ms |
144332 KB |
Output is correct |
11 |
Correct |
60 ms |
144364 KB |
Output is correct |
12 |
Correct |
64 ms |
144332 KB |
Output is correct |
13 |
Correct |
63 ms |
144428 KB |
Output is correct |
14 |
Correct |
58 ms |
144348 KB |
Output is correct |
15 |
Correct |
58 ms |
144284 KB |
Output is correct |
16 |
Correct |
59 ms |
144332 KB |
Output is correct |
17 |
Correct |
59 ms |
144312 KB |
Output is correct |
18 |
Correct |
66 ms |
144388 KB |
Output is correct |
19 |
Correct |
64 ms |
144624 KB |
Output is correct |
20 |
Correct |
67 ms |
144668 KB |
Output is correct |
21 |
Correct |
67 ms |
144752 KB |
Output is correct |
22 |
Correct |
74 ms |
144748 KB |
Output is correct |
23 |
Correct |
81 ms |
146036 KB |
Output is correct |
24 |
Correct |
71 ms |
146000 KB |
Output is correct |
25 |
Correct |
69 ms |
146124 KB |
Output is correct |
26 |
Correct |
78 ms |
146396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
144352 KB |
Output is correct |
2 |
Correct |
61 ms |
144308 KB |
Output is correct |
3 |
Correct |
60 ms |
144332 KB |
Output is correct |
4 |
Correct |
68 ms |
144392 KB |
Output is correct |
5 |
Correct |
106 ms |
144812 KB |
Output is correct |
6 |
Correct |
73 ms |
144376 KB |
Output is correct |
7 |
Correct |
67 ms |
144388 KB |
Output is correct |
8 |
Correct |
59 ms |
144540 KB |
Output is correct |
9 |
Correct |
59 ms |
144480 KB |
Output is correct |
10 |
Correct |
70 ms |
144568 KB |
Output is correct |
11 |
Correct |
121 ms |
144924 KB |
Output is correct |
12 |
Correct |
64 ms |
145720 KB |
Output is correct |
13 |
Correct |
62 ms |
145764 KB |
Output is correct |
14 |
Correct |
63 ms |
145860 KB |
Output is correct |
15 |
Correct |
87 ms |
146008 KB |
Output is correct |
16 |
Correct |
155 ms |
146436 KB |
Output is correct |
17 |
Correct |
182 ms |
167688 KB |
Output is correct |
18 |
Correct |
165 ms |
167684 KB |
Output is correct |
19 |
Correct |
177 ms |
169556 KB |
Output is correct |
20 |
Correct |
217 ms |
170412 KB |
Output is correct |
21 |
Correct |
421 ms |
170916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
144668 KB |
Output is correct |
2 |
Correct |
71 ms |
144644 KB |
Output is correct |
3 |
Correct |
121 ms |
145332 KB |
Output is correct |
4 |
Correct |
141 ms |
145992 KB |
Output is correct |
5 |
Correct |
70 ms |
147628 KB |
Output is correct |
6 |
Correct |
87 ms |
147652 KB |
Output is correct |
7 |
Correct |
141 ms |
148288 KB |
Output is correct |
8 |
Correct |
201 ms |
149076 KB |
Output is correct |
9 |
Correct |
102 ms |
159008 KB |
Output is correct |
10 |
Correct |
120 ms |
159248 KB |
Output is correct |
11 |
Correct |
202 ms |
159896 KB |
Output is correct |
12 |
Correct |
333 ms |
160636 KB |
Output is correct |
13 |
Correct |
148 ms |
172860 KB |
Output is correct |
14 |
Correct |
174 ms |
173772 KB |
Output is correct |
15 |
Correct |
259 ms |
174452 KB |
Output is correct |
16 |
Correct |
339 ms |
175420 KB |
Output is correct |
17 |
Correct |
394 ms |
174056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
617 ms |
173380 KB |
Output is correct |
2 |
Correct |
615 ms |
173372 KB |
Output is correct |
3 |
Correct |
542 ms |
173364 KB |
Output is correct |
4 |
Correct |
565 ms |
173368 KB |
Output is correct |
5 |
Correct |
644 ms |
172864 KB |
Output is correct |
6 |
Correct |
557 ms |
171012 KB |
Output is correct |
7 |
Correct |
622 ms |
176504 KB |
Output is correct |
8 |
Correct |
607 ms |
176472 KB |
Output is correct |
9 |
Correct |
600 ms |
176484 KB |
Output is correct |
10 |
Correct |
641 ms |
176576 KB |
Output is correct |
11 |
Correct |
614 ms |
175904 KB |
Output is correct |
12 |
Correct |
593 ms |
173220 KB |
Output is correct |
13 |
Correct |
663 ms |
181276 KB |
Output is correct |
14 |
Correct |
629 ms |
181136 KB |
Output is correct |
15 |
Correct |
738 ms |
181120 KB |
Output is correct |
16 |
Correct |
730 ms |
181124 KB |
Output is correct |
17 |
Correct |
703 ms |
180088 KB |
Output is correct |
18 |
Correct |
682 ms |
175144 KB |
Output is correct |
19 |
Correct |
714 ms |
181240 KB |
Output is correct |
20 |
Correct |
673 ms |
181308 KB |
Output is correct |
21 |
Correct |
665 ms |
181196 KB |
Output is correct |
22 |
Correct |
682 ms |
181152 KB |
Output is correct |
23 |
Correct |
754 ms |
180172 KB |
Output is correct |
24 |
Correct |
703 ms |
174924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
144296 KB |
Output is correct |
2 |
Correct |
59 ms |
144360 KB |
Output is correct |
3 |
Correct |
58 ms |
144312 KB |
Output is correct |
4 |
Correct |
57 ms |
144300 KB |
Output is correct |
5 |
Correct |
60 ms |
144340 KB |
Output is correct |
6 |
Correct |
58 ms |
144276 KB |
Output is correct |
7 |
Correct |
62 ms |
144364 KB |
Output is correct |
8 |
Correct |
56 ms |
144388 KB |
Output is correct |
9 |
Correct |
58 ms |
144268 KB |
Output is correct |
10 |
Correct |
60 ms |
144332 KB |
Output is correct |
11 |
Correct |
60 ms |
144364 KB |
Output is correct |
12 |
Correct |
64 ms |
144332 KB |
Output is correct |
13 |
Correct |
63 ms |
144428 KB |
Output is correct |
14 |
Correct |
58 ms |
144348 KB |
Output is correct |
15 |
Correct |
58 ms |
144284 KB |
Output is correct |
16 |
Correct |
59 ms |
144332 KB |
Output is correct |
17 |
Correct |
59 ms |
144312 KB |
Output is correct |
18 |
Correct |
66 ms |
144388 KB |
Output is correct |
19 |
Correct |
64 ms |
144624 KB |
Output is correct |
20 |
Correct |
67 ms |
144668 KB |
Output is correct |
21 |
Correct |
67 ms |
144752 KB |
Output is correct |
22 |
Correct |
74 ms |
144748 KB |
Output is correct |
23 |
Correct |
81 ms |
146036 KB |
Output is correct |
24 |
Correct |
71 ms |
146000 KB |
Output is correct |
25 |
Correct |
69 ms |
146124 KB |
Output is correct |
26 |
Correct |
78 ms |
146396 KB |
Output is correct |
27 |
Correct |
57 ms |
144352 KB |
Output is correct |
28 |
Correct |
61 ms |
144308 KB |
Output is correct |
29 |
Correct |
60 ms |
144332 KB |
Output is correct |
30 |
Correct |
68 ms |
144392 KB |
Output is correct |
31 |
Correct |
106 ms |
144812 KB |
Output is correct |
32 |
Correct |
73 ms |
144376 KB |
Output is correct |
33 |
Correct |
67 ms |
144388 KB |
Output is correct |
34 |
Correct |
59 ms |
144540 KB |
Output is correct |
35 |
Correct |
59 ms |
144480 KB |
Output is correct |
36 |
Correct |
70 ms |
144568 KB |
Output is correct |
37 |
Correct |
121 ms |
144924 KB |
Output is correct |
38 |
Correct |
64 ms |
145720 KB |
Output is correct |
39 |
Correct |
62 ms |
145764 KB |
Output is correct |
40 |
Correct |
63 ms |
145860 KB |
Output is correct |
41 |
Correct |
87 ms |
146008 KB |
Output is correct |
42 |
Correct |
155 ms |
146436 KB |
Output is correct |
43 |
Correct |
182 ms |
167688 KB |
Output is correct |
44 |
Correct |
165 ms |
167684 KB |
Output is correct |
45 |
Correct |
177 ms |
169556 KB |
Output is correct |
46 |
Correct |
217 ms |
170412 KB |
Output is correct |
47 |
Correct |
421 ms |
170916 KB |
Output is correct |
48 |
Correct |
60 ms |
144668 KB |
Output is correct |
49 |
Correct |
71 ms |
144644 KB |
Output is correct |
50 |
Correct |
121 ms |
145332 KB |
Output is correct |
51 |
Correct |
141 ms |
145992 KB |
Output is correct |
52 |
Correct |
70 ms |
147628 KB |
Output is correct |
53 |
Correct |
87 ms |
147652 KB |
Output is correct |
54 |
Correct |
141 ms |
148288 KB |
Output is correct |
55 |
Correct |
201 ms |
149076 KB |
Output is correct |
56 |
Correct |
102 ms |
159008 KB |
Output is correct |
57 |
Correct |
120 ms |
159248 KB |
Output is correct |
58 |
Correct |
202 ms |
159896 KB |
Output is correct |
59 |
Correct |
333 ms |
160636 KB |
Output is correct |
60 |
Correct |
148 ms |
172860 KB |
Output is correct |
61 |
Correct |
174 ms |
173772 KB |
Output is correct |
62 |
Correct |
259 ms |
174452 KB |
Output is correct |
63 |
Correct |
339 ms |
175420 KB |
Output is correct |
64 |
Correct |
394 ms |
174056 KB |
Output is correct |
65 |
Correct |
617 ms |
173380 KB |
Output is correct |
66 |
Correct |
615 ms |
173372 KB |
Output is correct |
67 |
Correct |
542 ms |
173364 KB |
Output is correct |
68 |
Correct |
565 ms |
173368 KB |
Output is correct |
69 |
Correct |
644 ms |
172864 KB |
Output is correct |
70 |
Correct |
557 ms |
171012 KB |
Output is correct |
71 |
Correct |
622 ms |
176504 KB |
Output is correct |
72 |
Correct |
607 ms |
176472 KB |
Output is correct |
73 |
Correct |
600 ms |
176484 KB |
Output is correct |
74 |
Correct |
641 ms |
176576 KB |
Output is correct |
75 |
Correct |
614 ms |
175904 KB |
Output is correct |
76 |
Correct |
593 ms |
173220 KB |
Output is correct |
77 |
Correct |
663 ms |
181276 KB |
Output is correct |
78 |
Correct |
629 ms |
181136 KB |
Output is correct |
79 |
Correct |
738 ms |
181120 KB |
Output is correct |
80 |
Correct |
730 ms |
181124 KB |
Output is correct |
81 |
Correct |
703 ms |
180088 KB |
Output is correct |
82 |
Correct |
682 ms |
175144 KB |
Output is correct |
83 |
Correct |
714 ms |
181240 KB |
Output is correct |
84 |
Correct |
673 ms |
181308 KB |
Output is correct |
85 |
Correct |
665 ms |
181196 KB |
Output is correct |
86 |
Correct |
682 ms |
181152 KB |
Output is correct |
87 |
Correct |
754 ms |
180172 KB |
Output is correct |
88 |
Correct |
703 ms |
174924 KB |
Output is correct |
89 |
Correct |
613 ms |
176516 KB |
Output is correct |
90 |
Correct |
577 ms |
176868 KB |
Output is correct |
91 |
Correct |
705 ms |
178568 KB |
Output is correct |
92 |
Correct |
626 ms |
178608 KB |
Output is correct |
93 |
Correct |
597 ms |
181364 KB |
Output is correct |
94 |
Correct |
681 ms |
180396 KB |
Output is correct |
95 |
Correct |
615 ms |
182048 KB |
Output is correct |
96 |
Correct |
722 ms |
181068 KB |
Output is correct |
97 |
Correct |
682 ms |
182012 KB |
Output is correct |
98 |
Correct |
719 ms |
184292 KB |
Output is correct |
99 |
Correct |
704 ms |
181680 KB |
Output is correct |
100 |
Correct |
737 ms |
181708 KB |
Output is correct |