#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;
in[depth][v] = ++tjm[depth];
niz[depth][in[depth][v]] = d;
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);
}
out[depth][v] = tjm[depth];
}
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});
}
}
multiset <ll> lengths[N+5];
multiset <ll> sol;
ll calc(int v){
if(lengths[v].size() == 0) return 0;
if(lengths[v].size() == 1) return *lengths[v].begin();
ll x = *lengths[v].rbegin();
ll d = x;
lengths[v].erase(lengths[v].find(x));
d += *lengths[v].rbegin();
lengths[v].insert(x);
return d;
}
ll rez[N+5];
ll dole[LOG+1][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++) seg[i].init(1, 1, n, 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].insert(dole[lg][c] = seg[lg].query(1, 1, n, in[lg][c], out[lg][c]));
}
sol.insert(rez[v] = calc(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];
sol.erase(sol.find(rez[v]));
lengths[v].erase(lengths[v].find(dole[lg][c]));
seg[lg].upd(1, 1, n, in[lg][b], out[lg][b], d - w[edg]);
lengths[v].insert(dole[lg][c] = seg[lg].query(1, 1, n, in[lg][c], out[lg][c]));
sol.insert(rez[v] = calc(v));
}
w[edg] = d;
res = *sol.rbegin();
cout << res << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7620 KB |
Output is correct |
2 |
Correct |
5 ms |
7628 KB |
Output is correct |
3 |
Correct |
4 ms |
7628 KB |
Output is correct |
4 |
Correct |
4 ms |
7628 KB |
Output is correct |
5 |
Correct |
4 ms |
7628 KB |
Output is correct |
6 |
Correct |
5 ms |
7628 KB |
Output is correct |
7 |
Correct |
5 ms |
7760 KB |
Output is correct |
8 |
Correct |
5 ms |
7756 KB |
Output is correct |
9 |
Correct |
5 ms |
7756 KB |
Output is correct |
10 |
Correct |
5 ms |
7752 KB |
Output is correct |
11 |
Correct |
5 ms |
7884 KB |
Output is correct |
12 |
Correct |
5 ms |
7756 KB |
Output is correct |
13 |
Correct |
5 ms |
7756 KB |
Output is correct |
14 |
Correct |
5 ms |
7756 KB |
Output is correct |
15 |
Correct |
5 ms |
7748 KB |
Output is correct |
16 |
Correct |
5 ms |
7760 KB |
Output is correct |
17 |
Correct |
5 ms |
7884 KB |
Output is correct |
18 |
Correct |
6 ms |
7880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7620 KB |
Output is correct |
2 |
Correct |
5 ms |
7628 KB |
Output is correct |
3 |
Correct |
4 ms |
7628 KB |
Output is correct |
4 |
Correct |
4 ms |
7628 KB |
Output is correct |
5 |
Correct |
4 ms |
7628 KB |
Output is correct |
6 |
Correct |
5 ms |
7628 KB |
Output is correct |
7 |
Correct |
5 ms |
7760 KB |
Output is correct |
8 |
Correct |
5 ms |
7756 KB |
Output is correct |
9 |
Correct |
5 ms |
7756 KB |
Output is correct |
10 |
Correct |
5 ms |
7752 KB |
Output is correct |
11 |
Correct |
5 ms |
7884 KB |
Output is correct |
12 |
Correct |
5 ms |
7756 KB |
Output is correct |
13 |
Correct |
5 ms |
7756 KB |
Output is correct |
14 |
Correct |
5 ms |
7756 KB |
Output is correct |
15 |
Correct |
5 ms |
7748 KB |
Output is correct |
16 |
Correct |
5 ms |
7760 KB |
Output is correct |
17 |
Correct |
5 ms |
7884 KB |
Output is correct |
18 |
Correct |
6 ms |
7880 KB |
Output is correct |
19 |
Correct |
36 ms |
8740 KB |
Output is correct |
20 |
Correct |
31 ms |
8780 KB |
Output is correct |
21 |
Correct |
45 ms |
8792 KB |
Output is correct |
22 |
Correct |
42 ms |
8880 KB |
Output is correct |
23 |
Correct |
52 ms |
13228 KB |
Output is correct |
24 |
Correct |
66 ms |
13892 KB |
Output is correct |
25 |
Correct |
71 ms |
14156 KB |
Output is correct |
26 |
Correct |
83 ms |
14728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7628 KB |
Output is correct |
2 |
Correct |
5 ms |
7628 KB |
Output is correct |
3 |
Correct |
6 ms |
7644 KB |
Output is correct |
4 |
Correct |
18 ms |
7840 KB |
Output is correct |
5 |
Correct |
73 ms |
8692 KB |
Output is correct |
6 |
Correct |
5 ms |
7628 KB |
Output is correct |
7 |
Correct |
6 ms |
7888 KB |
Output is correct |
8 |
Correct |
5 ms |
7884 KB |
Output is correct |
9 |
Correct |
7 ms |
7892 KB |
Output is correct |
10 |
Correct |
25 ms |
8012 KB |
Output is correct |
11 |
Correct |
106 ms |
9168 KB |
Output is correct |
12 |
Correct |
11 ms |
11084 KB |
Output is correct |
13 |
Correct |
13 ms |
11092 KB |
Output is correct |
14 |
Correct |
15 ms |
11084 KB |
Output is correct |
15 |
Correct |
39 ms |
11324 KB |
Output is correct |
16 |
Correct |
172 ms |
12424 KB |
Output is correct |
17 |
Correct |
159 ms |
67456 KB |
Output is correct |
18 |
Correct |
161 ms |
67448 KB |
Output is correct |
19 |
Correct |
165 ms |
67400 KB |
Output is correct |
20 |
Correct |
210 ms |
67668 KB |
Output is correct |
21 |
Correct |
551 ms |
68992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
8652 KB |
Output is correct |
2 |
Correct |
47 ms |
8788 KB |
Output is correct |
3 |
Correct |
211 ms |
9292 KB |
Output is correct |
4 |
Correct |
424 ms |
10004 KB |
Output is correct |
5 |
Correct |
32 ms |
19764 KB |
Output is correct |
6 |
Correct |
108 ms |
19972 KB |
Output is correct |
7 |
Correct |
446 ms |
20532 KB |
Output is correct |
8 |
Correct |
893 ms |
21316 KB |
Output is correct |
9 |
Correct |
121 ms |
64264 KB |
Output is correct |
10 |
Correct |
266 ms |
64576 KB |
Output is correct |
11 |
Correct |
922 ms |
65208 KB |
Output is correct |
12 |
Correct |
1687 ms |
66040 KB |
Output is correct |
13 |
Correct |
236 ms |
123384 KB |
Output is correct |
14 |
Correct |
403 ms |
124744 KB |
Output is correct |
15 |
Correct |
1212 ms |
125420 KB |
Output is correct |
16 |
Correct |
2272 ms |
126404 KB |
Output is correct |
17 |
Correct |
4854 ms |
125996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3674 ms |
125840 KB |
Output is correct |
2 |
Correct |
3765 ms |
127900 KB |
Output is correct |
3 |
Correct |
3614 ms |
125988 KB |
Output is correct |
4 |
Correct |
3751 ms |
128620 KB |
Output is correct |
5 |
Correct |
3772 ms |
124836 KB |
Output is correct |
6 |
Correct |
3376 ms |
115968 KB |
Output is correct |
7 |
Execution timed out |
5061 ms |
141484 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
7620 KB |
Output is correct |
2 |
Correct |
5 ms |
7628 KB |
Output is correct |
3 |
Correct |
4 ms |
7628 KB |
Output is correct |
4 |
Correct |
4 ms |
7628 KB |
Output is correct |
5 |
Correct |
4 ms |
7628 KB |
Output is correct |
6 |
Correct |
5 ms |
7628 KB |
Output is correct |
7 |
Correct |
5 ms |
7760 KB |
Output is correct |
8 |
Correct |
5 ms |
7756 KB |
Output is correct |
9 |
Correct |
5 ms |
7756 KB |
Output is correct |
10 |
Correct |
5 ms |
7752 KB |
Output is correct |
11 |
Correct |
5 ms |
7884 KB |
Output is correct |
12 |
Correct |
5 ms |
7756 KB |
Output is correct |
13 |
Correct |
5 ms |
7756 KB |
Output is correct |
14 |
Correct |
5 ms |
7756 KB |
Output is correct |
15 |
Correct |
5 ms |
7748 KB |
Output is correct |
16 |
Correct |
5 ms |
7760 KB |
Output is correct |
17 |
Correct |
5 ms |
7884 KB |
Output is correct |
18 |
Correct |
6 ms |
7880 KB |
Output is correct |
19 |
Correct |
36 ms |
8740 KB |
Output is correct |
20 |
Correct |
31 ms |
8780 KB |
Output is correct |
21 |
Correct |
45 ms |
8792 KB |
Output is correct |
22 |
Correct |
42 ms |
8880 KB |
Output is correct |
23 |
Correct |
52 ms |
13228 KB |
Output is correct |
24 |
Correct |
66 ms |
13892 KB |
Output is correct |
25 |
Correct |
71 ms |
14156 KB |
Output is correct |
26 |
Correct |
83 ms |
14728 KB |
Output is correct |
27 |
Correct |
4 ms |
7628 KB |
Output is correct |
28 |
Correct |
5 ms |
7628 KB |
Output is correct |
29 |
Correct |
6 ms |
7644 KB |
Output is correct |
30 |
Correct |
18 ms |
7840 KB |
Output is correct |
31 |
Correct |
73 ms |
8692 KB |
Output is correct |
32 |
Correct |
5 ms |
7628 KB |
Output is correct |
33 |
Correct |
6 ms |
7888 KB |
Output is correct |
34 |
Correct |
5 ms |
7884 KB |
Output is correct |
35 |
Correct |
7 ms |
7892 KB |
Output is correct |
36 |
Correct |
25 ms |
8012 KB |
Output is correct |
37 |
Correct |
106 ms |
9168 KB |
Output is correct |
38 |
Correct |
11 ms |
11084 KB |
Output is correct |
39 |
Correct |
13 ms |
11092 KB |
Output is correct |
40 |
Correct |
15 ms |
11084 KB |
Output is correct |
41 |
Correct |
39 ms |
11324 KB |
Output is correct |
42 |
Correct |
172 ms |
12424 KB |
Output is correct |
43 |
Correct |
159 ms |
67456 KB |
Output is correct |
44 |
Correct |
161 ms |
67448 KB |
Output is correct |
45 |
Correct |
165 ms |
67400 KB |
Output is correct |
46 |
Correct |
210 ms |
67668 KB |
Output is correct |
47 |
Correct |
551 ms |
68992 KB |
Output is correct |
48 |
Correct |
13 ms |
8652 KB |
Output is correct |
49 |
Correct |
47 ms |
8788 KB |
Output is correct |
50 |
Correct |
211 ms |
9292 KB |
Output is correct |
51 |
Correct |
424 ms |
10004 KB |
Output is correct |
52 |
Correct |
32 ms |
19764 KB |
Output is correct |
53 |
Correct |
108 ms |
19972 KB |
Output is correct |
54 |
Correct |
446 ms |
20532 KB |
Output is correct |
55 |
Correct |
893 ms |
21316 KB |
Output is correct |
56 |
Correct |
121 ms |
64264 KB |
Output is correct |
57 |
Correct |
266 ms |
64576 KB |
Output is correct |
58 |
Correct |
922 ms |
65208 KB |
Output is correct |
59 |
Correct |
1687 ms |
66040 KB |
Output is correct |
60 |
Correct |
236 ms |
123384 KB |
Output is correct |
61 |
Correct |
403 ms |
124744 KB |
Output is correct |
62 |
Correct |
1212 ms |
125420 KB |
Output is correct |
63 |
Correct |
2272 ms |
126404 KB |
Output is correct |
64 |
Correct |
4854 ms |
125996 KB |
Output is correct |
65 |
Correct |
3674 ms |
125840 KB |
Output is correct |
66 |
Correct |
3765 ms |
127900 KB |
Output is correct |
67 |
Correct |
3614 ms |
125988 KB |
Output is correct |
68 |
Correct |
3751 ms |
128620 KB |
Output is correct |
69 |
Correct |
3772 ms |
124836 KB |
Output is correct |
70 |
Correct |
3376 ms |
115968 KB |
Output is correct |
71 |
Execution timed out |
5061 ms |
141484 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |