#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
#define int ll
struct seg
{
int N; vector<int> st, lazy;
seg() {}
void init(int _N) {
N = _N;
st.resize(4 * N, 0);
lazy.resize(4 * N, 0);
}
void prop(int v, int l, int r) {
if(l == r || lazy[v] == 0) return;
st[v * 2] += lazy[v];
st[v * 2 + 1] += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int l, int r, int lo, int hi, int val) {
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
st[v] += val; lazy[v] += val;
return;
}
prop(v, l, r);
update(v * 2, l, (l + r) / 2, lo, hi, val);
update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
st[v] = max(st[v * 2], st[v * 2 + 1]);
}
int query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return st[v];
prop(v, l, r);
return max(query(v * 2, l, (l + r) / 2, lo, hi),
query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
};
int N, Q, W, S[100005]; seg ST[100005];
int A[100005], B[100005], C[100005];
int par[100005], tin[100005], out[100005];
vector<int> adj[100005], cur[100005];
vector<pair<int, int>> G[100005];
vector<array<int, 3>> E[100005];
set<pair<int, int>> ans[100005];
set<pair<int, int>> best;
int timer; vector<int> K;
bool rem[100005];
int dfs_size(int v, int p) {
S[v] = 1;
for(auto e : adj[v]) {
int u = A[e] ^ B[e] ^ v;
if(u == p || rem[u]) continue;
S[v] += dfs_size(u, v);
}
return S[v];
}
int dfs_centroid(int v, int p, int _N) {
for(auto e : adj[v]) {
int u = A[e] ^ B[e] ^ v;
if(u == p || rem[u]) continue;
if(S[u] * 2 > _N)
return dfs_centroid(u, v, _N);
}
return v;
}
void dfs(int v, int p) {
K.push_back(v); tin[v] = timer++;
for(auto e : adj[v]) {
int u = A[e] ^ B[e] ^ v;
if(u == p || rem[u]) continue;
par[u] = e; dfs(u, v);
}
out[v] = timer - 1;
}
void get(int v, int state) {
auto it = ans[v].rbegin();
int res = (*it).first;
if(ans[v].size() > 1) {
it++; res += (*it).first;
}
if(state) best.insert({res, v});
else best.erase({res, v});
}
void build(int v) {
int _N = dfs_size(v, v);
if(_N == 1) return;
int centroid = dfs_centroid(v, v, _N);
K.clear(); ST[centroid].init(_N); timer = 0;
par[centroid] = -1; dfs(centroid, centroid);
for(auto u : K) {
if(par[u] == -1) continue;
E[par[u]].push_back({tin[u], out[u], centroid});
ST[centroid].update(1, 0, _N - 1, tin[u], out[u], C[par[u]]);
}
int group = 0;
for(auto e : adj[centroid]) {
int u = A[e] ^ B[e] ^ centroid;
if(rem[u]) continue;
G[centroid].push_back({tin[u], out[u]});
int calc = ST[centroid].query(1, 0, _N - 1, tin[u], out[u]);
cur[centroid].push_back(calc);
ans[centroid].insert({calc, group++});
}
get(centroid, 1); rem[centroid] = 1;
for(auto e : adj[centroid]) {
int u = A[e] ^ B[e] ^ centroid;
if(rem[u]) continue;
build(u);
}
}
void upd(int I, int O, int D, int M) {
int lo = 0, hi = G[D].size() - 1, res = 0;
while(lo <= hi) {
int md = (lo + hi) / 2;
if(G[D][md].second < I)
lo = md + 1;
else hi = md - 1, res = md;
}
get(D, 0); ans[D].erase({cur[D][res], res});
ST[D].update(1, 0, ST[D].N - 1, I, O, M);
cur[D][res] = ST[D].query(1, 0, ST[D].N - 1, G[D][res].first, G[D][res].second);
ans[D].insert({cur[D][res], res}); get(D, 1);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> Q >> W;
for(int l = 1; l < N; l++) {
cin >> A[l] >> B[l] >> C[l];
adj[A[l]].push_back(l);
adj[B[l]].push_back(l);
}
build(1); int last = 0;
for(int l = 0; l < Q; l++) {
int d, e; cin >> d >> e;
d = (d + last) % (N - 1) + 1;
e = (e + last) % W;
for(auto u : E[d])
upd(u[0], u[1], u[2], e - C[d]);
C[d] = e; last = (*best.rbegin()).first;
cout << last << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19924 KB |
Output is correct |
2 |
Correct |
10 ms |
19924 KB |
Output is correct |
3 |
Correct |
10 ms |
19932 KB |
Output is correct |
4 |
Correct |
11 ms |
19912 KB |
Output is correct |
5 |
Correct |
10 ms |
19932 KB |
Output is correct |
6 |
Correct |
10 ms |
19932 KB |
Output is correct |
7 |
Correct |
11 ms |
19924 KB |
Output is correct |
8 |
Correct |
11 ms |
19948 KB |
Output is correct |
9 |
Correct |
11 ms |
19924 KB |
Output is correct |
10 |
Correct |
11 ms |
19924 KB |
Output is correct |
11 |
Correct |
13 ms |
19924 KB |
Output is correct |
12 |
Correct |
10 ms |
19924 KB |
Output is correct |
13 |
Correct |
10 ms |
19896 KB |
Output is correct |
14 |
Correct |
11 ms |
19924 KB |
Output is correct |
15 |
Correct |
12 ms |
19924 KB |
Output is correct |
16 |
Correct |
11 ms |
19928 KB |
Output is correct |
17 |
Correct |
11 ms |
20004 KB |
Output is correct |
18 |
Correct |
11 ms |
19988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19924 KB |
Output is correct |
2 |
Correct |
10 ms |
19924 KB |
Output is correct |
3 |
Correct |
10 ms |
19932 KB |
Output is correct |
4 |
Correct |
11 ms |
19912 KB |
Output is correct |
5 |
Correct |
10 ms |
19932 KB |
Output is correct |
6 |
Correct |
10 ms |
19932 KB |
Output is correct |
7 |
Correct |
11 ms |
19924 KB |
Output is correct |
8 |
Correct |
11 ms |
19948 KB |
Output is correct |
9 |
Correct |
11 ms |
19924 KB |
Output is correct |
10 |
Correct |
11 ms |
19924 KB |
Output is correct |
11 |
Correct |
13 ms |
19924 KB |
Output is correct |
12 |
Correct |
10 ms |
19924 KB |
Output is correct |
13 |
Correct |
10 ms |
19896 KB |
Output is correct |
14 |
Correct |
11 ms |
19924 KB |
Output is correct |
15 |
Correct |
12 ms |
19924 KB |
Output is correct |
16 |
Correct |
11 ms |
19928 KB |
Output is correct |
17 |
Correct |
11 ms |
20004 KB |
Output is correct |
18 |
Correct |
11 ms |
19988 KB |
Output is correct |
19 |
Correct |
26 ms |
20704 KB |
Output is correct |
20 |
Correct |
30 ms |
20752 KB |
Output is correct |
21 |
Correct |
34 ms |
20860 KB |
Output is correct |
22 |
Correct |
32 ms |
20968 KB |
Output is correct |
23 |
Correct |
44 ms |
24100 KB |
Output is correct |
24 |
Correct |
58 ms |
25172 KB |
Output is correct |
25 |
Correct |
67 ms |
25900 KB |
Output is correct |
26 |
Correct |
71 ms |
26724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19924 KB |
Output is correct |
2 |
Correct |
10 ms |
19924 KB |
Output is correct |
3 |
Correct |
11 ms |
19824 KB |
Output is correct |
4 |
Correct |
22 ms |
19944 KB |
Output is correct |
5 |
Correct |
69 ms |
20428 KB |
Output is correct |
6 |
Correct |
11 ms |
19820 KB |
Output is correct |
7 |
Correct |
11 ms |
20052 KB |
Output is correct |
8 |
Correct |
12 ms |
19976 KB |
Output is correct |
9 |
Correct |
12 ms |
20052 KB |
Output is correct |
10 |
Correct |
26 ms |
20136 KB |
Output is correct |
11 |
Correct |
88 ms |
20476 KB |
Output is correct |
12 |
Correct |
14 ms |
21372 KB |
Output is correct |
13 |
Correct |
14 ms |
21332 KB |
Output is correct |
14 |
Correct |
16 ms |
21416 KB |
Output is correct |
15 |
Correct |
41 ms |
21460 KB |
Output is correct |
16 |
Correct |
120 ms |
21848 KB |
Output is correct |
17 |
Correct |
115 ms |
48080 KB |
Output is correct |
18 |
Correct |
119 ms |
48056 KB |
Output is correct |
19 |
Correct |
117 ms |
48080 KB |
Output is correct |
20 |
Correct |
163 ms |
48132 KB |
Output is correct |
21 |
Correct |
359 ms |
48688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
20752 KB |
Output is correct |
2 |
Correct |
38 ms |
20820 KB |
Output is correct |
3 |
Correct |
141 ms |
21112 KB |
Output is correct |
4 |
Correct |
293 ms |
21356 KB |
Output is correct |
5 |
Correct |
49 ms |
32992 KB |
Output is correct |
6 |
Correct |
83 ms |
33100 KB |
Output is correct |
7 |
Correct |
279 ms |
33412 KB |
Output is correct |
8 |
Correct |
475 ms |
33576 KB |
Output is correct |
9 |
Correct |
215 ms |
93720 KB |
Output is correct |
10 |
Correct |
292 ms |
93828 KB |
Output is correct |
11 |
Correct |
567 ms |
94028 KB |
Output is correct |
12 |
Correct |
942 ms |
94428 KB |
Output is correct |
13 |
Correct |
475 ms |
173944 KB |
Output is correct |
14 |
Correct |
535 ms |
174128 KB |
Output is correct |
15 |
Correct |
921 ms |
174312 KB |
Output is correct |
16 |
Correct |
1389 ms |
174624 KB |
Output is correct |
17 |
Correct |
2675 ms |
174704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2241 ms |
146592 KB |
Output is correct |
2 |
Correct |
2408 ms |
150132 KB |
Output is correct |
3 |
Correct |
2351 ms |
149288 KB |
Output is correct |
4 |
Correct |
2357 ms |
149608 KB |
Output is correct |
5 |
Correct |
2282 ms |
142556 KB |
Output is correct |
6 |
Correct |
1944 ms |
101712 KB |
Output is correct |
7 |
Correct |
3060 ms |
175752 KB |
Output is correct |
8 |
Correct |
3086 ms |
175708 KB |
Output is correct |
9 |
Correct |
3153 ms |
175812 KB |
Output is correct |
10 |
Correct |
3182 ms |
174952 KB |
Output is correct |
11 |
Correct |
2981 ms |
165796 KB |
Output is correct |
12 |
Correct |
2565 ms |
115684 KB |
Output is correct |
13 |
Correct |
3355 ms |
187924 KB |
Output is correct |
14 |
Correct |
3291 ms |
187836 KB |
Output is correct |
15 |
Correct |
3342 ms |
187796 KB |
Output is correct |
16 |
Correct |
3320 ms |
186964 KB |
Output is correct |
17 |
Correct |
3201 ms |
176908 KB |
Output is correct |
18 |
Correct |
2526 ms |
121032 KB |
Output is correct |
19 |
Correct |
3244 ms |
187768 KB |
Output is correct |
20 |
Correct |
3492 ms |
187788 KB |
Output is correct |
21 |
Correct |
3285 ms |
187768 KB |
Output is correct |
22 |
Correct |
3384 ms |
186880 KB |
Output is correct |
23 |
Correct |
3168 ms |
176856 KB |
Output is correct |
24 |
Correct |
2601 ms |
120852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
19924 KB |
Output is correct |
2 |
Correct |
10 ms |
19924 KB |
Output is correct |
3 |
Correct |
10 ms |
19932 KB |
Output is correct |
4 |
Correct |
11 ms |
19912 KB |
Output is correct |
5 |
Correct |
10 ms |
19932 KB |
Output is correct |
6 |
Correct |
10 ms |
19932 KB |
Output is correct |
7 |
Correct |
11 ms |
19924 KB |
Output is correct |
8 |
Correct |
11 ms |
19948 KB |
Output is correct |
9 |
Correct |
11 ms |
19924 KB |
Output is correct |
10 |
Correct |
11 ms |
19924 KB |
Output is correct |
11 |
Correct |
13 ms |
19924 KB |
Output is correct |
12 |
Correct |
10 ms |
19924 KB |
Output is correct |
13 |
Correct |
10 ms |
19896 KB |
Output is correct |
14 |
Correct |
11 ms |
19924 KB |
Output is correct |
15 |
Correct |
12 ms |
19924 KB |
Output is correct |
16 |
Correct |
11 ms |
19928 KB |
Output is correct |
17 |
Correct |
11 ms |
20004 KB |
Output is correct |
18 |
Correct |
11 ms |
19988 KB |
Output is correct |
19 |
Correct |
26 ms |
20704 KB |
Output is correct |
20 |
Correct |
30 ms |
20752 KB |
Output is correct |
21 |
Correct |
34 ms |
20860 KB |
Output is correct |
22 |
Correct |
32 ms |
20968 KB |
Output is correct |
23 |
Correct |
44 ms |
24100 KB |
Output is correct |
24 |
Correct |
58 ms |
25172 KB |
Output is correct |
25 |
Correct |
67 ms |
25900 KB |
Output is correct |
26 |
Correct |
71 ms |
26724 KB |
Output is correct |
27 |
Correct |
10 ms |
19924 KB |
Output is correct |
28 |
Correct |
10 ms |
19924 KB |
Output is correct |
29 |
Correct |
11 ms |
19824 KB |
Output is correct |
30 |
Correct |
22 ms |
19944 KB |
Output is correct |
31 |
Correct |
69 ms |
20428 KB |
Output is correct |
32 |
Correct |
11 ms |
19820 KB |
Output is correct |
33 |
Correct |
11 ms |
20052 KB |
Output is correct |
34 |
Correct |
12 ms |
19976 KB |
Output is correct |
35 |
Correct |
12 ms |
20052 KB |
Output is correct |
36 |
Correct |
26 ms |
20136 KB |
Output is correct |
37 |
Correct |
88 ms |
20476 KB |
Output is correct |
38 |
Correct |
14 ms |
21372 KB |
Output is correct |
39 |
Correct |
14 ms |
21332 KB |
Output is correct |
40 |
Correct |
16 ms |
21416 KB |
Output is correct |
41 |
Correct |
41 ms |
21460 KB |
Output is correct |
42 |
Correct |
120 ms |
21848 KB |
Output is correct |
43 |
Correct |
115 ms |
48080 KB |
Output is correct |
44 |
Correct |
119 ms |
48056 KB |
Output is correct |
45 |
Correct |
117 ms |
48080 KB |
Output is correct |
46 |
Correct |
163 ms |
48132 KB |
Output is correct |
47 |
Correct |
359 ms |
48688 KB |
Output is correct |
48 |
Correct |
14 ms |
20752 KB |
Output is correct |
49 |
Correct |
38 ms |
20820 KB |
Output is correct |
50 |
Correct |
141 ms |
21112 KB |
Output is correct |
51 |
Correct |
293 ms |
21356 KB |
Output is correct |
52 |
Correct |
49 ms |
32992 KB |
Output is correct |
53 |
Correct |
83 ms |
33100 KB |
Output is correct |
54 |
Correct |
279 ms |
33412 KB |
Output is correct |
55 |
Correct |
475 ms |
33576 KB |
Output is correct |
56 |
Correct |
215 ms |
93720 KB |
Output is correct |
57 |
Correct |
292 ms |
93828 KB |
Output is correct |
58 |
Correct |
567 ms |
94028 KB |
Output is correct |
59 |
Correct |
942 ms |
94428 KB |
Output is correct |
60 |
Correct |
475 ms |
173944 KB |
Output is correct |
61 |
Correct |
535 ms |
174128 KB |
Output is correct |
62 |
Correct |
921 ms |
174312 KB |
Output is correct |
63 |
Correct |
1389 ms |
174624 KB |
Output is correct |
64 |
Correct |
2675 ms |
174704 KB |
Output is correct |
65 |
Correct |
2241 ms |
146592 KB |
Output is correct |
66 |
Correct |
2408 ms |
150132 KB |
Output is correct |
67 |
Correct |
2351 ms |
149288 KB |
Output is correct |
68 |
Correct |
2357 ms |
149608 KB |
Output is correct |
69 |
Correct |
2282 ms |
142556 KB |
Output is correct |
70 |
Correct |
1944 ms |
101712 KB |
Output is correct |
71 |
Correct |
3060 ms |
175752 KB |
Output is correct |
72 |
Correct |
3086 ms |
175708 KB |
Output is correct |
73 |
Correct |
3153 ms |
175812 KB |
Output is correct |
74 |
Correct |
3182 ms |
174952 KB |
Output is correct |
75 |
Correct |
2981 ms |
165796 KB |
Output is correct |
76 |
Correct |
2565 ms |
115684 KB |
Output is correct |
77 |
Correct |
3355 ms |
187924 KB |
Output is correct |
78 |
Correct |
3291 ms |
187836 KB |
Output is correct |
79 |
Correct |
3342 ms |
187796 KB |
Output is correct |
80 |
Correct |
3320 ms |
186964 KB |
Output is correct |
81 |
Correct |
3201 ms |
176908 KB |
Output is correct |
82 |
Correct |
2526 ms |
121032 KB |
Output is correct |
83 |
Correct |
3244 ms |
187768 KB |
Output is correct |
84 |
Correct |
3492 ms |
187788 KB |
Output is correct |
85 |
Correct |
3285 ms |
187768 KB |
Output is correct |
86 |
Correct |
3384 ms |
186880 KB |
Output is correct |
87 |
Correct |
3168 ms |
176856 KB |
Output is correct |
88 |
Correct |
2601 ms |
120852 KB |
Output is correct |
89 |
Correct |
2214 ms |
147880 KB |
Output is correct |
90 |
Correct |
2483 ms |
159388 KB |
Output is correct |
91 |
Correct |
2870 ms |
172088 KB |
Output is correct |
92 |
Correct |
3021 ms |
175580 KB |
Output is correct |
93 |
Correct |
3174 ms |
180076 KB |
Output is correct |
94 |
Correct |
3100 ms |
183512 KB |
Output is correct |
95 |
Correct |
3104 ms |
187744 KB |
Output is correct |
96 |
Correct |
3117 ms |
187944 KB |
Output is correct |
97 |
Correct |
3135 ms |
188160 KB |
Output is correct |
98 |
Correct |
3124 ms |
187896 KB |
Output is correct |
99 |
Correct |
3133 ms |
187656 KB |
Output is correct |
100 |
Correct |
3109 ms |
187676 KB |
Output is correct |