#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
#define int ll
const int N = 1e5 + 5;
const int C = 18;
vector<ar<int, 2>> edges[N];
struct ST{
vector<int> tree, add;
int N;
void init(int n){
N = n;
tree.resize(n << 2);
add.resize(n << 2);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
add[x << 1] += add[x];
add[x << 1 | 1] += add[x];
tree[x << 1] += add[x];
tree[x << 1 | 1] += add[x];
add[x] = 0;
}
void aad(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x] += v;
add[x] += v;
return;
}
push(x, lx, rx);
int m = (lx + rx) >> 1;
aad(l, r, v, lx, m, x << 1);
aad(l, r, v, m + 1, rx, x << 1 | 1);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
void aad(int l, int r, int v){
return aad(l, r, v, 0, N, 1);
}
int get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return tree[x];
push(x, lx, rx);
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get(int l, int r){
return get(l, r, 0, N, 1);
}
};
ST tree[N];
multiset<int> mx[N];
int par[N][C], sub[N], used[N];
int par2[N][C], ed[N][C], lvl;
int tin[N][C], tout[N][C], t;
vector<int> tt;
void dfs(int u, int p = -1){
if(p == -1){
tt.clear();
t = -1;
par[u][lvl] = u;
par2[u][lvl] = -1;
ed[u][lvl] = 0;
}
tin[u][lvl] = ++t;
sub[u] = 1;
tt.push_back(u);
for(auto x : edges[u]){
if(x[0] == p || used[x[0]]) continue;
par[x[0]][lvl] = par[u][lvl];
if(~par2[u][lvl]) par2[x[0]][lvl] = par2[u][lvl];
else par2[x[0]][lvl] = x[0];
ed[x[0]][lvl] = x[1];
dfs(x[0], u);
sub[u] += sub[x[0]];
}
tout[u][lvl] = t;
}
int cen(int u, int n, int p = -1){
for(auto x : edges[u]){
if(x[0] == p || used[x[0]]) continue;
if(sub[x[0]] * 2 > n) return cen(x[0], n, u);
} return u;
}
int res[N];
void dec(int u, int b = 0){ lvl = b;
dfs(u);
u = cen(u, sub[u]);
dfs(u);
//~ cout<<lvl<<" "<<u<<"\n";
tree[u].init(sub[u]);
for(auto x : tt){
tree[u].aad(tin[x][lvl], tout[x][lvl], ed[x][lvl]);
//~ cout<<x<<" "<<lvl<<" "<<ed[x][lvl]<<endl;
}
for(auto x : edges[u]){
if(used[x[0]]) continue;
mx[u].insert(tree[u].get(tin[x[0]][lvl], tout[x[0]][lvl]));
}
if((int)mx[u].size() > 1){
auto it = --mx[u].end();
res[u] = *it + *--it;
} else if((int)mx[u].size()){
res[u] = *--mx[u].end();
}
used[u] = 1;
for(auto x : edges[u]){
if(used[x[0]]) continue;
dec(x[0], b + 1);
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
multiset<int> ss;
int n, q, w; cin>>n>>q>>w;
vector<ar<int, 2>> E(n);
for(int i=1;i<n;i++){
int a, b, c; cin>>a>>b>>c;
edges[a].push_back({b, c});
edges[b].push_back({a, c});
E[i] = {a, b};
}
memset(par, -1, sizeof par);
dec(1);
for(int i=1;i<=n;i++){
ss.insert(res[i]);
}
auto upd = [&](int a, int b, int e){
for(int i=0;i<C;i++){
if(par[a][i] == -1 || par[b][i] == -1) continue;
if(tin[a][i] > tin[b][i]) swap(a, b);
int c = par[b][i];
int x = par2[b][i];
int old = tree[c].get(tin[x][i], tout[x][i]);
tree[c].aad(tin[b][i], tout[b][i], -ed[b][i] + e);
ed[b][i] = e;
mx[c].erase(mx[c].find(old));
mx[c].insert(tree[c].get(tin[x][i], tout[x][i]));
ss.erase(ss.find(res[c]));
if((int)mx[c].size() > 1){
auto it = --mx[c].end();
res[c] = *it + *--it;
} else if((int)mx[c].size()){
res[c] = *--mx[c].end();
}
ss.insert(res[c]);
}
};
//~ for(auto x : ss) cout<<x<<" ";
//~ cout<<endl;
int last = 0;
while(q--){
int v, e; cin>>v>>e;
v = (v + last) % (n - 1);
e = (e + last) % w;
upd(E[v + 1][0], E[v + 1][1], e);
//~ for(auto x : ss) cout<<x<<" ";
//~ cout<<endl;
last = *--ss.end();
cout<<last<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
26964 KB |
Output is correct |
2 |
Correct |
13 ms |
26964 KB |
Output is correct |
3 |
Correct |
13 ms |
26964 KB |
Output is correct |
4 |
Correct |
13 ms |
26984 KB |
Output is correct |
5 |
Correct |
12 ms |
26908 KB |
Output is correct |
6 |
Correct |
13 ms |
26964 KB |
Output is correct |
7 |
Correct |
13 ms |
26952 KB |
Output is correct |
8 |
Correct |
13 ms |
26964 KB |
Output is correct |
9 |
Correct |
13 ms |
26964 KB |
Output is correct |
10 |
Correct |
14 ms |
26964 KB |
Output is correct |
11 |
Correct |
13 ms |
26964 KB |
Output is correct |
12 |
Correct |
12 ms |
26964 KB |
Output is correct |
13 |
Correct |
13 ms |
27092 KB |
Output is correct |
14 |
Correct |
13 ms |
26964 KB |
Output is correct |
15 |
Correct |
13 ms |
27088 KB |
Output is correct |
16 |
Correct |
13 ms |
27032 KB |
Output is correct |
17 |
Correct |
13 ms |
27092 KB |
Output is correct |
18 |
Correct |
13 ms |
27092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
26964 KB |
Output is correct |
2 |
Correct |
13 ms |
26964 KB |
Output is correct |
3 |
Correct |
13 ms |
26964 KB |
Output is correct |
4 |
Correct |
13 ms |
26984 KB |
Output is correct |
5 |
Correct |
12 ms |
26908 KB |
Output is correct |
6 |
Correct |
13 ms |
26964 KB |
Output is correct |
7 |
Correct |
13 ms |
26952 KB |
Output is correct |
8 |
Correct |
13 ms |
26964 KB |
Output is correct |
9 |
Correct |
13 ms |
26964 KB |
Output is correct |
10 |
Correct |
14 ms |
26964 KB |
Output is correct |
11 |
Correct |
13 ms |
26964 KB |
Output is correct |
12 |
Correct |
12 ms |
26964 KB |
Output is correct |
13 |
Correct |
13 ms |
27092 KB |
Output is correct |
14 |
Correct |
13 ms |
26964 KB |
Output is correct |
15 |
Correct |
13 ms |
27088 KB |
Output is correct |
16 |
Correct |
13 ms |
27032 KB |
Output is correct |
17 |
Correct |
13 ms |
27092 KB |
Output is correct |
18 |
Correct |
13 ms |
27092 KB |
Output is correct |
19 |
Correct |
33 ms |
28116 KB |
Output is correct |
20 |
Correct |
34 ms |
28116 KB |
Output is correct |
21 |
Correct |
37 ms |
28276 KB |
Output is correct |
22 |
Correct |
40 ms |
28396 KB |
Output is correct |
23 |
Correct |
57 ms |
33056 KB |
Output is correct |
24 |
Correct |
70 ms |
33740 KB |
Output is correct |
25 |
Correct |
82 ms |
34060 KB |
Output is correct |
26 |
Correct |
81 ms |
34800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
26964 KB |
Output is correct |
2 |
Correct |
13 ms |
26964 KB |
Output is correct |
3 |
Correct |
17 ms |
26964 KB |
Output is correct |
4 |
Correct |
25 ms |
27088 KB |
Output is correct |
5 |
Correct |
71 ms |
27416 KB |
Output is correct |
6 |
Correct |
14 ms |
26964 KB |
Output is correct |
7 |
Correct |
14 ms |
27348 KB |
Output is correct |
8 |
Correct |
14 ms |
27368 KB |
Output is correct |
9 |
Correct |
18 ms |
27428 KB |
Output is correct |
10 |
Correct |
32 ms |
27476 KB |
Output is correct |
11 |
Correct |
103 ms |
27996 KB |
Output is correct |
12 |
Correct |
19 ms |
31444 KB |
Output is correct |
13 |
Correct |
23 ms |
31484 KB |
Output is correct |
14 |
Correct |
22 ms |
31420 KB |
Output is correct |
15 |
Correct |
49 ms |
31500 KB |
Output is correct |
16 |
Correct |
162 ms |
31980 KB |
Output is correct |
17 |
Correct |
190 ms |
116872 KB |
Output is correct |
18 |
Correct |
191 ms |
116980 KB |
Output is correct |
19 |
Correct |
207 ms |
116888 KB |
Output is correct |
20 |
Correct |
228 ms |
116984 KB |
Output is correct |
21 |
Correct |
504 ms |
117540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
28248 KB |
Output is correct |
2 |
Correct |
56 ms |
28364 KB |
Output is correct |
3 |
Correct |
187 ms |
28552 KB |
Output is correct |
4 |
Correct |
301 ms |
28880 KB |
Output is correct |
5 |
Correct |
54 ms |
41872 KB |
Output is correct |
6 |
Correct |
99 ms |
42016 KB |
Output is correct |
7 |
Correct |
297 ms |
42240 KB |
Output is correct |
8 |
Correct |
574 ms |
42540 KB |
Output is correct |
9 |
Correct |
274 ms |
109316 KB |
Output is correct |
10 |
Correct |
330 ms |
109448 KB |
Output is correct |
11 |
Correct |
754 ms |
109892 KB |
Output is correct |
12 |
Correct |
1175 ms |
109964 KB |
Output is correct |
13 |
Correct |
520 ms |
198112 KB |
Output is correct |
14 |
Correct |
635 ms |
198224 KB |
Output is correct |
15 |
Correct |
1031 ms |
198380 KB |
Output is correct |
16 |
Correct |
1747 ms |
198636 KB |
Output is correct |
17 |
Correct |
2628 ms |
198776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2539 ms |
175384 KB |
Output is correct |
2 |
Correct |
2615 ms |
177900 KB |
Output is correct |
3 |
Correct |
2547 ms |
176976 KB |
Output is correct |
4 |
Correct |
2702 ms |
177860 KB |
Output is correct |
5 |
Correct |
2659 ms |
173120 KB |
Output is correct |
6 |
Correct |
2259 ms |
149672 KB |
Output is correct |
7 |
Correct |
3433 ms |
201044 KB |
Output is correct |
8 |
Correct |
3301 ms |
200960 KB |
Output is correct |
9 |
Correct |
3482 ms |
201240 KB |
Output is correct |
10 |
Correct |
3469 ms |
200604 KB |
Output is correct |
11 |
Correct |
3309 ms |
194936 KB |
Output is correct |
12 |
Correct |
2956 ms |
162168 KB |
Output is correct |
13 |
Correct |
3715 ms |
213508 KB |
Output is correct |
14 |
Correct |
3811 ms |
213324 KB |
Output is correct |
15 |
Correct |
3590 ms |
213408 KB |
Output is correct |
16 |
Correct |
3369 ms |
212884 KB |
Output is correct |
17 |
Correct |
3497 ms |
205624 KB |
Output is correct |
18 |
Correct |
2968 ms |
166252 KB |
Output is correct |
19 |
Correct |
3464 ms |
213360 KB |
Output is correct |
20 |
Correct |
3421 ms |
213300 KB |
Output is correct |
21 |
Correct |
3410 ms |
213352 KB |
Output is correct |
22 |
Correct |
3409 ms |
212812 KB |
Output is correct |
23 |
Correct |
3493 ms |
205628 KB |
Output is correct |
24 |
Correct |
2925 ms |
166176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
26964 KB |
Output is correct |
2 |
Correct |
13 ms |
26964 KB |
Output is correct |
3 |
Correct |
13 ms |
26964 KB |
Output is correct |
4 |
Correct |
13 ms |
26984 KB |
Output is correct |
5 |
Correct |
12 ms |
26908 KB |
Output is correct |
6 |
Correct |
13 ms |
26964 KB |
Output is correct |
7 |
Correct |
13 ms |
26952 KB |
Output is correct |
8 |
Correct |
13 ms |
26964 KB |
Output is correct |
9 |
Correct |
13 ms |
26964 KB |
Output is correct |
10 |
Correct |
14 ms |
26964 KB |
Output is correct |
11 |
Correct |
13 ms |
26964 KB |
Output is correct |
12 |
Correct |
12 ms |
26964 KB |
Output is correct |
13 |
Correct |
13 ms |
27092 KB |
Output is correct |
14 |
Correct |
13 ms |
26964 KB |
Output is correct |
15 |
Correct |
13 ms |
27088 KB |
Output is correct |
16 |
Correct |
13 ms |
27032 KB |
Output is correct |
17 |
Correct |
13 ms |
27092 KB |
Output is correct |
18 |
Correct |
13 ms |
27092 KB |
Output is correct |
19 |
Correct |
33 ms |
28116 KB |
Output is correct |
20 |
Correct |
34 ms |
28116 KB |
Output is correct |
21 |
Correct |
37 ms |
28276 KB |
Output is correct |
22 |
Correct |
40 ms |
28396 KB |
Output is correct |
23 |
Correct |
57 ms |
33056 KB |
Output is correct |
24 |
Correct |
70 ms |
33740 KB |
Output is correct |
25 |
Correct |
82 ms |
34060 KB |
Output is correct |
26 |
Correct |
81 ms |
34800 KB |
Output is correct |
27 |
Correct |
15 ms |
26964 KB |
Output is correct |
28 |
Correct |
13 ms |
26964 KB |
Output is correct |
29 |
Correct |
17 ms |
26964 KB |
Output is correct |
30 |
Correct |
25 ms |
27088 KB |
Output is correct |
31 |
Correct |
71 ms |
27416 KB |
Output is correct |
32 |
Correct |
14 ms |
26964 KB |
Output is correct |
33 |
Correct |
14 ms |
27348 KB |
Output is correct |
34 |
Correct |
14 ms |
27368 KB |
Output is correct |
35 |
Correct |
18 ms |
27428 KB |
Output is correct |
36 |
Correct |
32 ms |
27476 KB |
Output is correct |
37 |
Correct |
103 ms |
27996 KB |
Output is correct |
38 |
Correct |
19 ms |
31444 KB |
Output is correct |
39 |
Correct |
23 ms |
31484 KB |
Output is correct |
40 |
Correct |
22 ms |
31420 KB |
Output is correct |
41 |
Correct |
49 ms |
31500 KB |
Output is correct |
42 |
Correct |
162 ms |
31980 KB |
Output is correct |
43 |
Correct |
190 ms |
116872 KB |
Output is correct |
44 |
Correct |
191 ms |
116980 KB |
Output is correct |
45 |
Correct |
207 ms |
116888 KB |
Output is correct |
46 |
Correct |
228 ms |
116984 KB |
Output is correct |
47 |
Correct |
504 ms |
117540 KB |
Output is correct |
48 |
Correct |
18 ms |
28248 KB |
Output is correct |
49 |
Correct |
56 ms |
28364 KB |
Output is correct |
50 |
Correct |
187 ms |
28552 KB |
Output is correct |
51 |
Correct |
301 ms |
28880 KB |
Output is correct |
52 |
Correct |
54 ms |
41872 KB |
Output is correct |
53 |
Correct |
99 ms |
42016 KB |
Output is correct |
54 |
Correct |
297 ms |
42240 KB |
Output is correct |
55 |
Correct |
574 ms |
42540 KB |
Output is correct |
56 |
Correct |
274 ms |
109316 KB |
Output is correct |
57 |
Correct |
330 ms |
109448 KB |
Output is correct |
58 |
Correct |
754 ms |
109892 KB |
Output is correct |
59 |
Correct |
1175 ms |
109964 KB |
Output is correct |
60 |
Correct |
520 ms |
198112 KB |
Output is correct |
61 |
Correct |
635 ms |
198224 KB |
Output is correct |
62 |
Correct |
1031 ms |
198380 KB |
Output is correct |
63 |
Correct |
1747 ms |
198636 KB |
Output is correct |
64 |
Correct |
2628 ms |
198776 KB |
Output is correct |
65 |
Correct |
2539 ms |
175384 KB |
Output is correct |
66 |
Correct |
2615 ms |
177900 KB |
Output is correct |
67 |
Correct |
2547 ms |
176976 KB |
Output is correct |
68 |
Correct |
2702 ms |
177860 KB |
Output is correct |
69 |
Correct |
2659 ms |
173120 KB |
Output is correct |
70 |
Correct |
2259 ms |
149672 KB |
Output is correct |
71 |
Correct |
3433 ms |
201044 KB |
Output is correct |
72 |
Correct |
3301 ms |
200960 KB |
Output is correct |
73 |
Correct |
3482 ms |
201240 KB |
Output is correct |
74 |
Correct |
3469 ms |
200604 KB |
Output is correct |
75 |
Correct |
3309 ms |
194936 KB |
Output is correct |
76 |
Correct |
2956 ms |
162168 KB |
Output is correct |
77 |
Correct |
3715 ms |
213508 KB |
Output is correct |
78 |
Correct |
3811 ms |
213324 KB |
Output is correct |
79 |
Correct |
3590 ms |
213408 KB |
Output is correct |
80 |
Correct |
3369 ms |
212884 KB |
Output is correct |
81 |
Correct |
3497 ms |
205624 KB |
Output is correct |
82 |
Correct |
2968 ms |
166252 KB |
Output is correct |
83 |
Correct |
3464 ms |
213360 KB |
Output is correct |
84 |
Correct |
3421 ms |
213300 KB |
Output is correct |
85 |
Correct |
3410 ms |
213352 KB |
Output is correct |
86 |
Correct |
3409 ms |
212812 KB |
Output is correct |
87 |
Correct |
3493 ms |
205628 KB |
Output is correct |
88 |
Correct |
2925 ms |
166176 KB |
Output is correct |
89 |
Correct |
2481 ms |
176284 KB |
Output is correct |
90 |
Correct |
2750 ms |
185324 KB |
Output is correct |
91 |
Correct |
3275 ms |
197068 KB |
Output is correct |
92 |
Correct |
3514 ms |
200012 KB |
Output is correct |
93 |
Correct |
3818 ms |
205620 KB |
Output is correct |
94 |
Correct |
3606 ms |
206580 KB |
Output is correct |
95 |
Correct |
3453 ms |
210832 KB |
Output is correct |
96 |
Correct |
3543 ms |
209792 KB |
Output is correct |
97 |
Correct |
3346 ms |
210776 KB |
Output is correct |
98 |
Correct |
3445 ms |
213056 KB |
Output is correct |
99 |
Correct |
3333 ms |
210508 KB |
Output is correct |
100 |
Correct |
3416 ms |
210516 KB |
Output is correct |