#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
int n,q,in[100005],out[100005],mx;
ll W,d[100005],val[100005];
vector<pii> adj[100005];
pii edge[100005];
vector<int> v;
struct node {
ll ans,suff,pref,lca,depth;
} s[2000000];
ll lz[2000000];
node merge(node a, node b) {
node res;
res.depth=max(a.depth,b.depth); //d[x]
res.lca=min(a.lca,b.lca); //d[y]
res.pref=max({a.pref,b.pref,b.depth-2*a.lca}); //d[x]-2d[y]
res.suff=max({a.suff,b.suff,a.depth-2*b.lca}); //-2d[y]+d[z]
res.ans=max({a.ans,b.ans,a.depth+b.pref,a.suff+b.depth}); //d[x]-2d[y]+d[z]
return res;
}
void push(int l, int r, int idx) {
if (lz[idx]==0) return;
s[idx].depth+=lz[idx];
s[idx].lca+=lz[idx];
s[idx].suff-=lz[idx];
s[idx].pref-=lz[idx];
if (l!=r) {
lz[2*idx]+=lz[idx];
lz[2*idx+1]+=lz[idx];
}
lz[idx]=0;
}
void build(int l, int r, int idx) {
if (l==r) {
s[idx].depth=d[v[l]];
s[idx].lca=d[v[l]];
s[idx].pref=-d[v[l]];
s[idx].suff=-d[v[l]];
s[idx].ans=-2e18-5;
} else {
int mid=(l+r)/2;
build(l,mid,2*idx);
build(mid+1,r,2*idx+1);
s[idx]=merge(s[2*idx],s[2*idx+1]);
}
}
void update(int l, int r, int idx, int x, int y, ll val) {
push(l,r,idx);
if (x>r || y<l) return;
if (x<=l && r<=y) {
lz[idx]+=val;
push(l,r,idx);
} else {
int mid=(l+r)/2;
update(l,mid,2*idx,x,y,val);
update(mid+1,r,2*idx+1,x,y,val);
s[idx]=merge(s[2*idx],s[2*idx+1]);
}
}
void dfs(int x, int par) {
in[x]=v.size();
v.push_back(x);
for (auto s : adj[x]) {
if (s.first==par) continue;
d[s.first]=d[x]+s.second;
dfs(s.first,x);
v.push_back(x);
}
out[x]=v.size()-1;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>q>>W;
for (int i=0; i<n-1; ++i) {
int a,b; ll w;
cin>>a>>b>>w;
adj[a].push_back(pii(b,w));
adj[b].push_back(pii(a,w));
edge[i]=pii(a,b);
val[i]=w;
}
dfs(1,0);
mx=v.size()-1;
build(0,mx,1);
ll bef=0;
while (q--) {
ll x,w; cin>>x>>w;
x=(x+bef)%(n-1);
w=(w+bef)%W;
int a=edge[x].first, b=edge[x].second;
if (d[a]>d[b]) swap(a,b);
update(0,mx,1,in[b],out[b],w-val[x]);
val[x]=w;
bef=max(s[1].ans,s[1].depth);
cout<<bef<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2696 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2696 KB |
Output is correct |
6 |
Correct |
1 ms |
2684 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2696 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2688 KB |
Output is correct |
13 |
Correct |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2696 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2696 KB |
Output is correct |
6 |
Correct |
1 ms |
2684 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2696 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2688 KB |
Output is correct |
13 |
Correct |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
4 ms |
3056 KB |
Output is correct |
20 |
Correct |
4 ms |
3028 KB |
Output is correct |
21 |
Correct |
5 ms |
3028 KB |
Output is correct |
22 |
Correct |
5 ms |
3156 KB |
Output is correct |
23 |
Correct |
7 ms |
4948 KB |
Output is correct |
24 |
Correct |
7 ms |
4904 KB |
Output is correct |
25 |
Correct |
10 ms |
5040 KB |
Output is correct |
26 |
Correct |
8 ms |
5264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2692 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 ms |
2744 KB |
Output is correct |
4 |
Correct |
7 ms |
2828 KB |
Output is correct |
5 |
Correct |
33 ms |
3752 KB |
Output is correct |
6 |
Correct |
1 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2824 KB |
Output is correct |
8 |
Correct |
2 ms |
2820 KB |
Output is correct |
9 |
Correct |
2 ms |
2772 KB |
Output is correct |
10 |
Correct |
10 ms |
3100 KB |
Output is correct |
11 |
Correct |
44 ms |
4144 KB |
Output is correct |
12 |
Correct |
3 ms |
4608 KB |
Output is correct |
13 |
Correct |
4 ms |
4692 KB |
Output is correct |
14 |
Correct |
5 ms |
4820 KB |
Output is correct |
15 |
Correct |
14 ms |
5040 KB |
Output is correct |
16 |
Correct |
56 ms |
6188 KB |
Output is correct |
17 |
Correct |
38 ms |
34872 KB |
Output is correct |
18 |
Correct |
38 ms |
35236 KB |
Output is correct |
19 |
Correct |
41 ms |
37188 KB |
Output is correct |
20 |
Correct |
61 ms |
38220 KB |
Output is correct |
21 |
Correct |
133 ms |
39480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3028 KB |
Output is correct |
2 |
Correct |
8 ms |
3156 KB |
Output is correct |
3 |
Correct |
32 ms |
3640 KB |
Output is correct |
4 |
Correct |
61 ms |
4352 KB |
Output is correct |
5 |
Correct |
7 ms |
6996 KB |
Output is correct |
6 |
Correct |
13 ms |
7124 KB |
Output is correct |
7 |
Correct |
44 ms |
7792 KB |
Output is correct |
8 |
Correct |
84 ms |
8604 KB |
Output is correct |
9 |
Correct |
25 ms |
20888 KB |
Output is correct |
10 |
Correct |
34 ms |
21064 KB |
Output is correct |
11 |
Correct |
72 ms |
21828 KB |
Output is correct |
12 |
Correct |
129 ms |
22660 KB |
Output is correct |
13 |
Correct |
45 ms |
38292 KB |
Output is correct |
14 |
Correct |
56 ms |
39316 KB |
Output is correct |
15 |
Correct |
99 ms |
39940 KB |
Output is correct |
16 |
Correct |
151 ms |
40812 KB |
Output is correct |
17 |
Correct |
133 ms |
39624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
43020 KB |
Output is correct |
2 |
Correct |
185 ms |
43012 KB |
Output is correct |
3 |
Correct |
178 ms |
42940 KB |
Output is correct |
4 |
Correct |
183 ms |
42932 KB |
Output is correct |
5 |
Correct |
174 ms |
42472 KB |
Output is correct |
6 |
Correct |
156 ms |
40752 KB |
Output is correct |
7 |
Correct |
209 ms |
45492 KB |
Output is correct |
8 |
Correct |
198 ms |
45384 KB |
Output is correct |
9 |
Correct |
248 ms |
45424 KB |
Output is correct |
10 |
Correct |
194 ms |
45372 KB |
Output is correct |
11 |
Correct |
205 ms |
44784 KB |
Output is correct |
12 |
Correct |
194 ms |
42392 KB |
Output is correct |
13 |
Correct |
233 ms |
49084 KB |
Output is correct |
14 |
Correct |
238 ms |
49152 KB |
Output is correct |
15 |
Correct |
251 ms |
49120 KB |
Output is correct |
16 |
Correct |
246 ms |
49084 KB |
Output is correct |
17 |
Correct |
225 ms |
48320 KB |
Output is correct |
18 |
Correct |
212 ms |
43840 KB |
Output is correct |
19 |
Correct |
239 ms |
49084 KB |
Output is correct |
20 |
Correct |
229 ms |
49052 KB |
Output is correct |
21 |
Correct |
230 ms |
49216 KB |
Output is correct |
22 |
Correct |
238 ms |
49104 KB |
Output is correct |
23 |
Correct |
236 ms |
48520 KB |
Output is correct |
24 |
Correct |
198 ms |
43740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2696 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2696 KB |
Output is correct |
6 |
Correct |
1 ms |
2684 KB |
Output is correct |
7 |
Correct |
1 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
1 ms |
2696 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2688 KB |
Output is correct |
13 |
Correct |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
4 ms |
3056 KB |
Output is correct |
20 |
Correct |
4 ms |
3028 KB |
Output is correct |
21 |
Correct |
5 ms |
3028 KB |
Output is correct |
22 |
Correct |
5 ms |
3156 KB |
Output is correct |
23 |
Correct |
7 ms |
4948 KB |
Output is correct |
24 |
Correct |
7 ms |
4904 KB |
Output is correct |
25 |
Correct |
10 ms |
5040 KB |
Output is correct |
26 |
Correct |
8 ms |
5264 KB |
Output is correct |
27 |
Correct |
2 ms |
2692 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
3 ms |
2744 KB |
Output is correct |
30 |
Correct |
7 ms |
2828 KB |
Output is correct |
31 |
Correct |
33 ms |
3752 KB |
Output is correct |
32 |
Correct |
1 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2824 KB |
Output is correct |
34 |
Correct |
2 ms |
2820 KB |
Output is correct |
35 |
Correct |
2 ms |
2772 KB |
Output is correct |
36 |
Correct |
10 ms |
3100 KB |
Output is correct |
37 |
Correct |
44 ms |
4144 KB |
Output is correct |
38 |
Correct |
3 ms |
4608 KB |
Output is correct |
39 |
Correct |
4 ms |
4692 KB |
Output is correct |
40 |
Correct |
5 ms |
4820 KB |
Output is correct |
41 |
Correct |
14 ms |
5040 KB |
Output is correct |
42 |
Correct |
56 ms |
6188 KB |
Output is correct |
43 |
Correct |
38 ms |
34872 KB |
Output is correct |
44 |
Correct |
38 ms |
35236 KB |
Output is correct |
45 |
Correct |
41 ms |
37188 KB |
Output is correct |
46 |
Correct |
61 ms |
38220 KB |
Output is correct |
47 |
Correct |
133 ms |
39480 KB |
Output is correct |
48 |
Correct |
2 ms |
3028 KB |
Output is correct |
49 |
Correct |
8 ms |
3156 KB |
Output is correct |
50 |
Correct |
32 ms |
3640 KB |
Output is correct |
51 |
Correct |
61 ms |
4352 KB |
Output is correct |
52 |
Correct |
7 ms |
6996 KB |
Output is correct |
53 |
Correct |
13 ms |
7124 KB |
Output is correct |
54 |
Correct |
44 ms |
7792 KB |
Output is correct |
55 |
Correct |
84 ms |
8604 KB |
Output is correct |
56 |
Correct |
25 ms |
20888 KB |
Output is correct |
57 |
Correct |
34 ms |
21064 KB |
Output is correct |
58 |
Correct |
72 ms |
21828 KB |
Output is correct |
59 |
Correct |
129 ms |
22660 KB |
Output is correct |
60 |
Correct |
45 ms |
38292 KB |
Output is correct |
61 |
Correct |
56 ms |
39316 KB |
Output is correct |
62 |
Correct |
99 ms |
39940 KB |
Output is correct |
63 |
Correct |
151 ms |
40812 KB |
Output is correct |
64 |
Correct |
133 ms |
39624 KB |
Output is correct |
65 |
Correct |
178 ms |
43020 KB |
Output is correct |
66 |
Correct |
185 ms |
43012 KB |
Output is correct |
67 |
Correct |
178 ms |
42940 KB |
Output is correct |
68 |
Correct |
183 ms |
42932 KB |
Output is correct |
69 |
Correct |
174 ms |
42472 KB |
Output is correct |
70 |
Correct |
156 ms |
40752 KB |
Output is correct |
71 |
Correct |
209 ms |
45492 KB |
Output is correct |
72 |
Correct |
198 ms |
45384 KB |
Output is correct |
73 |
Correct |
248 ms |
45424 KB |
Output is correct |
74 |
Correct |
194 ms |
45372 KB |
Output is correct |
75 |
Correct |
205 ms |
44784 KB |
Output is correct |
76 |
Correct |
194 ms |
42392 KB |
Output is correct |
77 |
Correct |
233 ms |
49084 KB |
Output is correct |
78 |
Correct |
238 ms |
49152 KB |
Output is correct |
79 |
Correct |
251 ms |
49120 KB |
Output is correct |
80 |
Correct |
246 ms |
49084 KB |
Output is correct |
81 |
Correct |
225 ms |
48320 KB |
Output is correct |
82 |
Correct |
212 ms |
43840 KB |
Output is correct |
83 |
Correct |
239 ms |
49084 KB |
Output is correct |
84 |
Correct |
229 ms |
49052 KB |
Output is correct |
85 |
Correct |
230 ms |
49216 KB |
Output is correct |
86 |
Correct |
238 ms |
49104 KB |
Output is correct |
87 |
Correct |
236 ms |
48520 KB |
Output is correct |
88 |
Correct |
198 ms |
43740 KB |
Output is correct |
89 |
Correct |
181 ms |
42012 KB |
Output is correct |
90 |
Correct |
206 ms |
42344 KB |
Output is correct |
91 |
Correct |
205 ms |
43636 KB |
Output is correct |
92 |
Correct |
219 ms |
43708 KB |
Output is correct |
93 |
Correct |
213 ms |
45904 KB |
Output is correct |
94 |
Correct |
246 ms |
45052 KB |
Output is correct |
95 |
Correct |
246 ms |
46600 KB |
Output is correct |
96 |
Correct |
242 ms |
45576 KB |
Output is correct |
97 |
Correct |
231 ms |
46436 KB |
Output is correct |
98 |
Correct |
301 ms |
48360 KB |
Output is correct |
99 |
Correct |
270 ms |
46248 KB |
Output is correct |
100 |
Correct |
232 ms |
46276 KB |
Output is correct |