#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 100000;
const int LOG = 18;
vector <pair <int, int>> graf[N+5];
int sz[N+5], A[N+5], B[N+5];
ll w[N+5];
bool erased[N+5];
void dfs_size(int v, int p){
sz[v] = 1;
for(auto pr : graf[v]){
int c = pr.first;
if(erased[c] || c == p) continue;
dfs_size(c, v);
sz[v] += sz[c];
}
}
int find_centroid(int v, int p, int sve){ for(auto c : graf[v]) if(!erased[c.first] && c.first != p && 2*sz[c.first] > sve) return find_centroid(c.first, v, sve); return v; }
int in[LOG+1][N+5], out[LOG+1][N+5], par[LOG+1][N+5], kome[LOG+1][N+5];
ll niz[LOG+1][N+5];
int tjm[LOG+1];
struct Segment{
ll val[4*N+5];
ll lazy[4*N+5];
void propagate(int node, int l, int r){
val[node] += lazy[node];
if(l == r){
lazy[node] = 0;
return;
}
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
lazy[node] = 0;
}
void init(int node, int l, int r, int lg){
if(l == r){
val[node] = niz[lg][l];
return;
}
int mid = (l+r)/2;
init(node*2, l, mid, lg);
init(node*2+1, mid+1, r, lg);
val[node] = max(val[node*2], val[node*2+1]);
}
void upd(int node, int l, int r, int tl, int tr, ll v){
propagate(node, l, r);
if(tl > r || l > tr) return;
if(tl <= l && r <= tr){
lazy[node] += v;
propagate(node, l, r);
return;
}
int mid = (l+r)/2;
upd(node*2, l, mid, tl, tr, v);
upd(node*2+1, mid+1, r, tl, tr, v);
val[node] = max(val[node*2], val[node*2+1]);
}
ll query(int node, int l, int r, int tl, int tr){
propagate(node, l, r);
if(tl > r || l > tr) return 0;
if(tl <= l && r <= tr) return val[node];
int mid = (l+r)/2;
return max(query(node*2, l, mid, tl, tr), query(node*2+1, mid+1, r, tl, tr));
}
} seg[LOG+1];
void dfs_depth(int v, int p, ll d, int depth, int root){
par[depth][v] = p;
kome[depth][v] = root;
for(auto pr : graf[v]){
int c, dc;
tie(c, dc) = pr;
if(erased[c] || c == p) continue;
dfs_depth(c, v, d + w[dc], depth, root);
if(!in[depth][v]) in[depth][v] = in[depth][c];
out[depth][v] = out[depth][c];
}
if(!in[depth][v]){
in[depth][v] = out[depth][v] = ++tjm[depth];
niz[depth][in[depth][v]] = d;
}
}
int kd[N+5];
void decompose(){
queue <pair <int, int>> q;
q.push({1, 1});
while(!q.empty()){
int v, d;
tie(v, d) = q.front();
q.pop();
dfs_size(v, 0);
v = find_centroid(v, 0, sz[v]);
kd[v] = d;
for(auto c : graf[v]){
if(erased[c.first]) continue;
dfs_depth(c.first, v, w[c.second], d, c.first);
}
erased[v] = 1;
for(auto c : graf[v]) if(!erased[c.first]) q.push({c.first, d + 1});
}
}
priority_queue <pair <ll, int>> lengths[N+5];
priority_queue <pair <ll, int>> sol;
ll dole[LOG+1][N+5];
ll calc(int v){
int lg = kd[v];
while(!lengths[v].empty() && dole[lg][lengths[v].top().second] != lengths[v].top().first) lengths[v].pop();
if(lengths[v].empty()) return 0;
ll x;
int c;
tie(x, c) = lengths[v].top();
lengths[v].pop();
while(!lengths[v].empty() && (dole[lg][lengths[v].top().second] != lengths[v].top().first || lengths[v].top().second == c)) lengths[v].pop();
if(lengths[v].empty()){
lengths[v].push({x, c});
return x;
}
ll y = lengths[v].top().first;
lengths[v].push({x, c});
return x + y;
}
ll rez[N+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, qrs;
ll W;
cin >> n >> qrs >> W;
for(int i=1; i<n; i++){
int a, b;
ll c;
cin >> a >> b >> c;
graf[a].push_back({b, i});
graf[b].push_back({a, i});
w[i] = c;
A[i] = a;
B[i] = b;
}
decompose();
for(int i=1; i<=LOG; i++) if(tjm[i]) seg[i].init(1, 1, tjm[i], i);
for(int v=1; v<=n; v++){
int lg = kd[v];
for(auto pr : graf[v]){
int c = pr.first;
if(kd[c] <= lg) continue;
lengths[v].push({dole[lg][c] = seg[lg].query(1, 1, tjm[lg], in[lg][c], out[lg][c]), c});
}
sol.push({rez[v] = calc(v), v});
}
ll res = 0;
while(qrs--){
int edg;
ll d;
cin >> edg >> d;
edg = 1 + (edg + res)%(n-1);
d = (d + res)%W;
int a = A[edg], b = B[edg];
for(int lg=1; lg<=LOG; lg++){
if(kd[a] < lg || kd[b] < lg) break;
if(par[lg][a] == b) swap(a, b);
int c = kome[lg][b];
int v = par[lg][c];
seg[lg].upd(1, 1, tjm[lg], in[lg][b], out[lg][b], d - w[edg]);
lengths[v].push({dole[lg][c] = seg[lg].query(1, 1, tjm[lg], in[lg][c], out[lg][c]), c});
sol.push({rez[v] = calc(v), v});
}
while(!sol.empty() && rez[sol.top().second] != sol.top().first) sol.pop();
res = sol.top().first;
w[edg] = d;
cout << res << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5964 KB |
Output is correct |
2 |
Correct |
3 ms |
6012 KB |
Output is correct |
3 |
Correct |
3 ms |
5964 KB |
Output is correct |
4 |
Correct |
3 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5964 KB |
Output is correct |
6 |
Correct |
3 ms |
5964 KB |
Output is correct |
7 |
Correct |
3 ms |
5964 KB |
Output is correct |
8 |
Correct |
4 ms |
6092 KB |
Output is correct |
9 |
Correct |
4 ms |
6092 KB |
Output is correct |
10 |
Correct |
4 ms |
6112 KB |
Output is correct |
11 |
Correct |
3 ms |
6092 KB |
Output is correct |
12 |
Correct |
4 ms |
6092 KB |
Output is correct |
13 |
Correct |
4 ms |
6108 KB |
Output is correct |
14 |
Correct |
4 ms |
6092 KB |
Output is correct |
15 |
Correct |
4 ms |
6092 KB |
Output is correct |
16 |
Correct |
4 ms |
6092 KB |
Output is correct |
17 |
Correct |
4 ms |
6092 KB |
Output is correct |
18 |
Correct |
3 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5964 KB |
Output is correct |
2 |
Correct |
3 ms |
6012 KB |
Output is correct |
3 |
Correct |
3 ms |
5964 KB |
Output is correct |
4 |
Correct |
3 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5964 KB |
Output is correct |
6 |
Correct |
3 ms |
5964 KB |
Output is correct |
7 |
Correct |
3 ms |
5964 KB |
Output is correct |
8 |
Correct |
4 ms |
6092 KB |
Output is correct |
9 |
Correct |
4 ms |
6092 KB |
Output is correct |
10 |
Correct |
4 ms |
6112 KB |
Output is correct |
11 |
Correct |
3 ms |
6092 KB |
Output is correct |
12 |
Correct |
4 ms |
6092 KB |
Output is correct |
13 |
Correct |
4 ms |
6108 KB |
Output is correct |
14 |
Correct |
4 ms |
6092 KB |
Output is correct |
15 |
Correct |
4 ms |
6092 KB |
Output is correct |
16 |
Correct |
4 ms |
6092 KB |
Output is correct |
17 |
Correct |
4 ms |
6092 KB |
Output is correct |
18 |
Correct |
3 ms |
6092 KB |
Output is correct |
19 |
Correct |
23 ms |
6984 KB |
Output is correct |
20 |
Correct |
24 ms |
7068 KB |
Output is correct |
21 |
Correct |
28 ms |
7124 KB |
Output is correct |
22 |
Correct |
21 ms |
7340 KB |
Output is correct |
23 |
Correct |
37 ms |
9028 KB |
Output is correct |
24 |
Correct |
46 ms |
9380 KB |
Output is correct |
25 |
Correct |
53 ms |
10216 KB |
Output is correct |
26 |
Correct |
46 ms |
9916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5836 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
5 ms |
5836 KB |
Output is correct |
4 |
Correct |
18 ms |
6092 KB |
Output is correct |
5 |
Correct |
77 ms |
6764 KB |
Output is correct |
6 |
Correct |
3 ms |
5836 KB |
Output is correct |
7 |
Correct |
4 ms |
5964 KB |
Output is correct |
8 |
Correct |
4 ms |
5964 KB |
Output is correct |
9 |
Correct |
6 ms |
5964 KB |
Output is correct |
10 |
Correct |
22 ms |
6428 KB |
Output is correct |
11 |
Correct |
97 ms |
7428 KB |
Output is correct |
12 |
Correct |
8 ms |
6972 KB |
Output is correct |
13 |
Correct |
7 ms |
6860 KB |
Output is correct |
14 |
Correct |
9 ms |
6900 KB |
Output is correct |
15 |
Correct |
30 ms |
7144 KB |
Output is correct |
16 |
Correct |
124 ms |
8140 KB |
Output is correct |
17 |
Correct |
78 ms |
24644 KB |
Output is correct |
18 |
Correct |
79 ms |
24608 KB |
Output is correct |
19 |
Correct |
84 ms |
24612 KB |
Output is correct |
20 |
Correct |
115 ms |
24632 KB |
Output is correct |
21 |
Correct |
245 ms |
27088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
6732 KB |
Output is correct |
2 |
Correct |
43 ms |
7204 KB |
Output is correct |
3 |
Correct |
192 ms |
8980 KB |
Output is correct |
4 |
Correct |
374 ms |
11152 KB |
Output is correct |
5 |
Correct |
23 ms |
12744 KB |
Output is correct |
6 |
Correct |
79 ms |
13616 KB |
Output is correct |
7 |
Correct |
333 ms |
17200 KB |
Output is correct |
8 |
Correct |
670 ms |
21740 KB |
Output is correct |
9 |
Correct |
87 ms |
39728 KB |
Output is correct |
10 |
Correct |
190 ms |
41084 KB |
Output is correct |
11 |
Correct |
611 ms |
43840 KB |
Output is correct |
12 |
Correct |
1154 ms |
48384 KB |
Output is correct |
13 |
Correct |
172 ms |
76540 KB |
Output is correct |
14 |
Correct |
288 ms |
79408 KB |
Output is correct |
15 |
Correct |
883 ms |
84464 KB |
Output is correct |
16 |
Correct |
1603 ms |
85016 KB |
Output is correct |
17 |
Correct |
3201 ms |
118344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2501 ms |
96320 KB |
Output is correct |
2 |
Correct |
2763 ms |
98196 KB |
Output is correct |
3 |
Correct |
2548 ms |
96904 KB |
Output is correct |
4 |
Correct |
2554 ms |
99412 KB |
Output is correct |
5 |
Correct |
2516 ms |
96912 KB |
Output is correct |
6 |
Correct |
2244 ms |
104212 KB |
Output is correct |
7 |
Correct |
3348 ms |
120196 KB |
Output is correct |
8 |
Correct |
3225 ms |
125500 KB |
Output is correct |
9 |
Correct |
3226 ms |
126316 KB |
Output is correct |
10 |
Correct |
3339 ms |
120792 KB |
Output is correct |
11 |
Correct |
3183 ms |
116892 KB |
Output is correct |
12 |
Correct |
2892 ms |
103688 KB |
Output is correct |
13 |
Correct |
2144 ms |
101328 KB |
Output is correct |
14 |
Correct |
2136 ms |
101480 KB |
Output is correct |
15 |
Correct |
2244 ms |
101748 KB |
Output is correct |
16 |
Correct |
2358 ms |
102020 KB |
Output is correct |
17 |
Correct |
2240 ms |
101824 KB |
Output is correct |
18 |
Correct |
1959 ms |
98248 KB |
Output is correct |
19 |
Correct |
2154 ms |
101432 KB |
Output is correct |
20 |
Correct |
2106 ms |
101380 KB |
Output is correct |
21 |
Correct |
2200 ms |
101896 KB |
Output is correct |
22 |
Correct |
2416 ms |
102280 KB |
Output is correct |
23 |
Correct |
2269 ms |
101704 KB |
Output is correct |
24 |
Correct |
1906 ms |
98096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5964 KB |
Output is correct |
2 |
Correct |
3 ms |
6012 KB |
Output is correct |
3 |
Correct |
3 ms |
5964 KB |
Output is correct |
4 |
Correct |
3 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5964 KB |
Output is correct |
6 |
Correct |
3 ms |
5964 KB |
Output is correct |
7 |
Correct |
3 ms |
5964 KB |
Output is correct |
8 |
Correct |
4 ms |
6092 KB |
Output is correct |
9 |
Correct |
4 ms |
6092 KB |
Output is correct |
10 |
Correct |
4 ms |
6112 KB |
Output is correct |
11 |
Correct |
3 ms |
6092 KB |
Output is correct |
12 |
Correct |
4 ms |
6092 KB |
Output is correct |
13 |
Correct |
4 ms |
6108 KB |
Output is correct |
14 |
Correct |
4 ms |
6092 KB |
Output is correct |
15 |
Correct |
4 ms |
6092 KB |
Output is correct |
16 |
Correct |
4 ms |
6092 KB |
Output is correct |
17 |
Correct |
4 ms |
6092 KB |
Output is correct |
18 |
Correct |
3 ms |
6092 KB |
Output is correct |
19 |
Correct |
23 ms |
6984 KB |
Output is correct |
20 |
Correct |
24 ms |
7068 KB |
Output is correct |
21 |
Correct |
28 ms |
7124 KB |
Output is correct |
22 |
Correct |
21 ms |
7340 KB |
Output is correct |
23 |
Correct |
37 ms |
9028 KB |
Output is correct |
24 |
Correct |
46 ms |
9380 KB |
Output is correct |
25 |
Correct |
53 ms |
10216 KB |
Output is correct |
26 |
Correct |
46 ms |
9916 KB |
Output is correct |
27 |
Correct |
3 ms |
5836 KB |
Output is correct |
28 |
Correct |
3 ms |
5836 KB |
Output is correct |
29 |
Correct |
5 ms |
5836 KB |
Output is correct |
30 |
Correct |
18 ms |
6092 KB |
Output is correct |
31 |
Correct |
77 ms |
6764 KB |
Output is correct |
32 |
Correct |
3 ms |
5836 KB |
Output is correct |
33 |
Correct |
4 ms |
5964 KB |
Output is correct |
34 |
Correct |
4 ms |
5964 KB |
Output is correct |
35 |
Correct |
6 ms |
5964 KB |
Output is correct |
36 |
Correct |
22 ms |
6428 KB |
Output is correct |
37 |
Correct |
97 ms |
7428 KB |
Output is correct |
38 |
Correct |
8 ms |
6972 KB |
Output is correct |
39 |
Correct |
7 ms |
6860 KB |
Output is correct |
40 |
Correct |
9 ms |
6900 KB |
Output is correct |
41 |
Correct |
30 ms |
7144 KB |
Output is correct |
42 |
Correct |
124 ms |
8140 KB |
Output is correct |
43 |
Correct |
78 ms |
24644 KB |
Output is correct |
44 |
Correct |
79 ms |
24608 KB |
Output is correct |
45 |
Correct |
84 ms |
24612 KB |
Output is correct |
46 |
Correct |
115 ms |
24632 KB |
Output is correct |
47 |
Correct |
245 ms |
27088 KB |
Output is correct |
48 |
Correct |
8 ms |
6732 KB |
Output is correct |
49 |
Correct |
43 ms |
7204 KB |
Output is correct |
50 |
Correct |
192 ms |
8980 KB |
Output is correct |
51 |
Correct |
374 ms |
11152 KB |
Output is correct |
52 |
Correct |
23 ms |
12744 KB |
Output is correct |
53 |
Correct |
79 ms |
13616 KB |
Output is correct |
54 |
Correct |
333 ms |
17200 KB |
Output is correct |
55 |
Correct |
670 ms |
21740 KB |
Output is correct |
56 |
Correct |
87 ms |
39728 KB |
Output is correct |
57 |
Correct |
190 ms |
41084 KB |
Output is correct |
58 |
Correct |
611 ms |
43840 KB |
Output is correct |
59 |
Correct |
1154 ms |
48384 KB |
Output is correct |
60 |
Correct |
172 ms |
76540 KB |
Output is correct |
61 |
Correct |
288 ms |
79408 KB |
Output is correct |
62 |
Correct |
883 ms |
84464 KB |
Output is correct |
63 |
Correct |
1603 ms |
85016 KB |
Output is correct |
64 |
Correct |
3201 ms |
118344 KB |
Output is correct |
65 |
Correct |
2501 ms |
96320 KB |
Output is correct |
66 |
Correct |
2763 ms |
98196 KB |
Output is correct |
67 |
Correct |
2548 ms |
96904 KB |
Output is correct |
68 |
Correct |
2554 ms |
99412 KB |
Output is correct |
69 |
Correct |
2516 ms |
96912 KB |
Output is correct |
70 |
Correct |
2244 ms |
104212 KB |
Output is correct |
71 |
Correct |
3348 ms |
120196 KB |
Output is correct |
72 |
Correct |
3225 ms |
125500 KB |
Output is correct |
73 |
Correct |
3226 ms |
126316 KB |
Output is correct |
74 |
Correct |
3339 ms |
120792 KB |
Output is correct |
75 |
Correct |
3183 ms |
116892 KB |
Output is correct |
76 |
Correct |
2892 ms |
103688 KB |
Output is correct |
77 |
Correct |
2144 ms |
101328 KB |
Output is correct |
78 |
Correct |
2136 ms |
101480 KB |
Output is correct |
79 |
Correct |
2244 ms |
101748 KB |
Output is correct |
80 |
Correct |
2358 ms |
102020 KB |
Output is correct |
81 |
Correct |
2240 ms |
101824 KB |
Output is correct |
82 |
Correct |
1959 ms |
98248 KB |
Output is correct |
83 |
Correct |
2154 ms |
101432 KB |
Output is correct |
84 |
Correct |
2106 ms |
101380 KB |
Output is correct |
85 |
Correct |
2200 ms |
101896 KB |
Output is correct |
86 |
Correct |
2416 ms |
102280 KB |
Output is correct |
87 |
Correct |
2269 ms |
101704 KB |
Output is correct |
88 |
Correct |
1906 ms |
98096 KB |
Output is correct |
89 |
Correct |
2564 ms |
101132 KB |
Output is correct |
90 |
Correct |
2823 ms |
123456 KB |
Output is correct |
91 |
Correct |
3127 ms |
126028 KB |
Output is correct |
92 |
Correct |
3208 ms |
126148 KB |
Output is correct |
93 |
Correct |
3092 ms |
113056 KB |
Output is correct |
94 |
Correct |
2844 ms |
113512 KB |
Output is correct |
95 |
Correct |
2059 ms |
98520 KB |
Output is correct |
96 |
Correct |
2104 ms |
98544 KB |
Output is correct |
97 |
Correct |
2071 ms |
98596 KB |
Output is correct |
98 |
Correct |
2073 ms |
100904 KB |
Output is correct |
99 |
Correct |
2082 ms |
98716 KB |
Output is correct |
100 |
Correct |
2107 ms |
98584 KB |
Output is correct |