#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target ("avx2")
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second
typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
int N, Q, sz[MM], bk[MM], pa[MM], in[LOG][MM], ot[LOG][MM], cp[LOG][MM], tp[LOG][MM], mp[MM], ct;
vector<int> adj[MM]; ll av[MM], W;
multiset<ll> ast;
struct node {
ll lz;
pair<ll,int> mx;
};
struct tree {
vector<node> seg;
int wt;
inline void prop(int i, int l, int r) {
if(l!=r) {
seg[lc].lz+=seg[i].lz;
seg[rc].lz+=seg[i].lz; }
seg[i].mx.f+=seg[i].lz;
seg[i].lz=0;
}
void build(int i, int sl, int sr) {
if(sl==sr) {
seg[i].mx=make_pair(0,mp[sl]);
return; }
int m=sl+sr>>1;
build(rc, m+1, sr);
build(lc, sl, m);
calc(i);
}
inline void calc(int i) {
seg[i].mx=max(seg[lc].mx, seg[rc].mx);
}
void upd(int i, int sl, int sr, int l, int r, ll v) {
prop(i, sl, sr);
if(l>sr || r<sl) return;
if(l<=sl&&sr<=r) {
seg[i].lz+=v;
prop(i, sl, sr); return; }
int m=sl+sr>>1;
upd(rc, m+1, sr, l, r, v);
upd(lc, sl, m, l, r, v);
calc(i);
}
pair<ll,int> rmq(int i, int sl, int sr, int l, int r) {
if(l>sr || r<sl) return {0,0};
prop(i, sl, sr);
if(l<=sl&&sr<=r) return seg[i].mx;
int m=sl+sr>>1;
return max(rmq(lc, sl, m, l, r), rmq(rc, m+1, sr, l, r));
}
void init(int n) {
wt=n;
seg.resize(4*n+4);
build(1, 1, n);
}
} st[MM];
int crt(int u, int th, int fa) {
for(int &v:adj[u]) if(v!=fa&&!bk[v]&&sz[v]>th) {
return crt(v, th, u); }
return u;
}
void dfs(int u, int fa) {
sz[u]=1;
for(int &v:adj[u]) if(v!=fa&&!bk[v]) {
dfs(v, u);
sz[u]+=sz[v];
}
}
void etr(int u, int fa, int lvl, int rt, int tv) {
in[lvl][u]=++ct; cp[lvl][u]=rt; tp[lvl][u]=tv; mp[ct]=u;
for(int &v:adj[u]) if(v!=fa&&!bk[v]) {
etr(v, u, lvl, rt, tv); }
ot[lvl][u]=ct;
}
void rec(int rt, int nds, int fa=-1, int lvl=0) {
if(nds<=1) return; dfs(rt, 0);
rt=crt(rt, nds/2, 0); pa[rt]=fa;
// cout<<rt<<el;
bk[rt]=true; ct=0;
// get ett
cp[lvl][rt]=tp[lvl][rt]=rt;
for(int &v:adj[rt]) if(!bk[v]) etr(v, rt, lvl, rt, v);
if(ct==0) return;
// construct tree
st[rt].init(ct);
int tally=0, lv=-1;
for(int &v:adj[rt]) if(!bk[v]) {
if(sz[v]<sz[rt]) {
tally+=sz[v];
rec(v, sz[v], rt, lvl+1); }
else lv=v; }
if(~lv) rec(lv, nds-tally-1, rt, lvl+1);
}
void qry(int u, int v, ll val) {
// find smallest component
int cur=0;
while(cur<LOG-1&&cp[cur+1][u]==cp[cur+1][v]&&cp[cur+1][u]!=0) ++cur;
// cout<<"iterating on "<<u<<" starting with "<<cur<<" delta "<<val<<el;
// jump
int crt=cp[cur][u];
while(cur>=0) {
// update edge
// cout<<"crt "<<crt<<el;
int w=(in[cur][u]>in[cur][v]?u:v);
// cout<<"level "<<cur<<" w "<<w<<" cent "<<crt<<" updating "<<in[cur][w]<<" "<<ot[cur][w]<<el;
st[crt].upd(1, 1, st[crt].wt, in[cur][w], ot[cur][w], val);
// query max
auto x=st[crt].rmq(1, 1, st[crt].wt, 1, st[crt].wt);
// cout<<"x value "<<x.f<<" "<<x.s<<" "<<tp[cur][x.s]<<" "<<in[cur][tp[cur][x.s]]<<" "<<ot[cur][tp[cur][x.s]]<<el;
auto y=max(st[crt].rmq(1, 1, st[crt].wt, 1, in[cur][tp[cur][x.s]]-1), st[crt].rmq(1, 1, st[crt].wt, ot[cur][tp[cur][x.s]]+1, st[crt].wt));
//cout<<"y value "<<y.f<<" "<<x.s<<el;
ll cnd=x.f+y.f;
if(cnd!=av[crt]) {
ast.erase(ast.find(av[crt]));
ast.insert(av[crt]=cnd);
}
crt=pa[crt]; cur--;
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>N>>Q>>W;
vector<pair<ll,pair<int,int>>> edg;
for(int i=1; i<N; ++i) {
ll u, v, w; cin>>u>>v>>w;
adj[u].pb(v); adj[v].pb(u);
edg.pb({w,{u,v}});
}
// preprocess
rec(1, N);
for(int i=1; i<=N; ++i) ast.insert(0);
for(auto &e:edg) qry(e.s.f, e.s.s, e.f);
ll last=0, e, w;
for(int q=1; q<=Q; ++q) {
cin>>e>>w;
e=(e+last)%(N-1);
w=(w+last)%W;
qry(edg[e].s.f, edg[e].s.s, w-edg[e].f);
last=*ast.rbegin(); edg[e].f=w;
cout<<last<<el;
}
}
Compilation message
diameter.cpp: In member function 'void tree::build(int, int, int)':
diameter.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int m=sl+sr>>1;
| ~~^~~
diameter.cpp: In member function 'void tree::upd(int, int, int, int, int, ll)':
diameter.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int m=sl+sr>>1;
| ~~^~~
diameter.cpp: In member function 'std::pair<long long int, int> tree::rmq(int, int, int, int, int)':
diameter.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int m=sl+sr>>1;
| ~~^~~
diameter.cpp: In function 'void rec(int, int, int, int)':
diameter.cpp:101:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
101 | if(nds<=1) return; dfs(rt, 0);
| ^~
diameter.cpp:101:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
101 | if(nds<=1) return; dfs(rt, 0);
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5836 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5836 KB |
Output is correct |
5 |
Correct |
3 ms |
5836 KB |
Output is correct |
6 |
Correct |
3 ms |
5836 KB |
Output is correct |
7 |
Correct |
4 ms |
5836 KB |
Output is correct |
8 |
Correct |
3 ms |
5836 KB |
Output is correct |
9 |
Correct |
3 ms |
5836 KB |
Output is correct |
10 |
Correct |
4 ms |
5836 KB |
Output is correct |
11 |
Correct |
3 ms |
5836 KB |
Output is correct |
12 |
Correct |
3 ms |
5964 KB |
Output is correct |
13 |
Correct |
4 ms |
5964 KB |
Output is correct |
14 |
Correct |
5 ms |
5956 KB |
Output is correct |
15 |
Correct |
3 ms |
5964 KB |
Output is correct |
16 |
Correct |
4 ms |
5964 KB |
Output is correct |
17 |
Correct |
4 ms |
5964 KB |
Output is correct |
18 |
Correct |
5 ms |
5964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5836 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5836 KB |
Output is correct |
5 |
Correct |
3 ms |
5836 KB |
Output is correct |
6 |
Correct |
3 ms |
5836 KB |
Output is correct |
7 |
Correct |
4 ms |
5836 KB |
Output is correct |
8 |
Correct |
3 ms |
5836 KB |
Output is correct |
9 |
Correct |
3 ms |
5836 KB |
Output is correct |
10 |
Correct |
4 ms |
5836 KB |
Output is correct |
11 |
Correct |
3 ms |
5836 KB |
Output is correct |
12 |
Correct |
3 ms |
5964 KB |
Output is correct |
13 |
Correct |
4 ms |
5964 KB |
Output is correct |
14 |
Correct |
5 ms |
5956 KB |
Output is correct |
15 |
Correct |
3 ms |
5964 KB |
Output is correct |
16 |
Correct |
4 ms |
5964 KB |
Output is correct |
17 |
Correct |
4 ms |
5964 KB |
Output is correct |
18 |
Correct |
5 ms |
5964 KB |
Output is correct |
19 |
Correct |
20 ms |
6732 KB |
Output is correct |
20 |
Correct |
22 ms |
6848 KB |
Output is correct |
21 |
Correct |
25 ms |
6988 KB |
Output is correct |
22 |
Correct |
22 ms |
7156 KB |
Output is correct |
23 |
Correct |
43 ms |
10264 KB |
Output is correct |
24 |
Correct |
60 ms |
11452 KB |
Output is correct |
25 |
Correct |
66 ms |
12020 KB |
Output is correct |
26 |
Correct |
73 ms |
13000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5836 KB |
Output is correct |
2 |
Correct |
3 ms |
5856 KB |
Output is correct |
3 |
Correct |
4 ms |
5836 KB |
Output is correct |
4 |
Correct |
12 ms |
5836 KB |
Output is correct |
5 |
Correct |
49 ms |
6188 KB |
Output is correct |
6 |
Correct |
3 ms |
5836 KB |
Output is correct |
7 |
Correct |
3 ms |
5964 KB |
Output is correct |
8 |
Correct |
4 ms |
5964 KB |
Output is correct |
9 |
Correct |
5 ms |
5856 KB |
Output is correct |
10 |
Correct |
21 ms |
5996 KB |
Output is correct |
11 |
Correct |
80 ms |
6392 KB |
Output is correct |
12 |
Correct |
8 ms |
6860 KB |
Output is correct |
13 |
Correct |
8 ms |
6928 KB |
Output is correct |
14 |
Correct |
11 ms |
6988 KB |
Output is correct |
15 |
Correct |
30 ms |
6976 KB |
Output is correct |
16 |
Correct |
116 ms |
7396 KB |
Output is correct |
17 |
Correct |
158 ms |
27300 KB |
Output is correct |
18 |
Correct |
129 ms |
27320 KB |
Output is correct |
19 |
Correct |
141 ms |
27380 KB |
Output is correct |
20 |
Correct |
167 ms |
27456 KB |
Output is correct |
21 |
Correct |
268 ms |
28036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
6860 KB |
Output is correct |
2 |
Correct |
29 ms |
6988 KB |
Output is correct |
3 |
Correct |
112 ms |
7108 KB |
Output is correct |
4 |
Correct |
221 ms |
7468 KB |
Output is correct |
5 |
Correct |
63 ms |
19144 KB |
Output is correct |
6 |
Correct |
93 ms |
19212 KB |
Output is correct |
7 |
Correct |
268 ms |
19400 KB |
Output is correct |
8 |
Correct |
536 ms |
19848 KB |
Output is correct |
9 |
Correct |
361 ms |
84492 KB |
Output is correct |
10 |
Correct |
401 ms |
84704 KB |
Output is correct |
11 |
Correct |
670 ms |
84828 KB |
Output is correct |
12 |
Correct |
1130 ms |
85128 KB |
Output is correct |
13 |
Correct |
768 ms |
173800 KB |
Output is correct |
14 |
Correct |
839 ms |
173780 KB |
Output is correct |
15 |
Correct |
1162 ms |
173964 KB |
Output is correct |
16 |
Correct |
1642 ms |
174384 KB |
Output is correct |
17 |
Correct |
2180 ms |
174232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3027 ms |
139044 KB |
Output is correct |
2 |
Correct |
3079 ms |
143408 KB |
Output is correct |
3 |
Correct |
3032 ms |
141108 KB |
Output is correct |
4 |
Correct |
3205 ms |
143828 KB |
Output is correct |
5 |
Correct |
3021 ms |
135208 KB |
Output is correct |
6 |
Correct |
2231 ms |
99608 KB |
Output is correct |
7 |
Correct |
4459 ms |
178332 KB |
Output is correct |
8 |
Correct |
4458 ms |
182324 KB |
Output is correct |
9 |
Correct |
4374 ms |
182448 KB |
Output is correct |
10 |
Correct |
4245 ms |
181764 KB |
Output is correct |
11 |
Correct |
3857 ms |
172764 KB |
Output is correct |
12 |
Correct |
3051 ms |
123728 KB |
Output is correct |
13 |
Correct |
4062 ms |
197220 KB |
Output is correct |
14 |
Correct |
4334 ms |
197240 KB |
Output is correct |
15 |
Correct |
4109 ms |
197224 KB |
Output is correct |
16 |
Correct |
4075 ms |
196488 KB |
Output is correct |
17 |
Correct |
3993 ms |
186352 KB |
Output is correct |
18 |
Correct |
3292 ms |
129656 KB |
Output is correct |
19 |
Correct |
4413 ms |
197172 KB |
Output is correct |
20 |
Correct |
4290 ms |
197188 KB |
Output is correct |
21 |
Correct |
4210 ms |
197400 KB |
Output is correct |
22 |
Correct |
4270 ms |
196440 KB |
Output is correct |
23 |
Correct |
4070 ms |
186228 KB |
Output is correct |
24 |
Correct |
3073 ms |
129668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5836 KB |
Output is correct |
2 |
Correct |
3 ms |
5836 KB |
Output is correct |
3 |
Correct |
3 ms |
5836 KB |
Output is correct |
4 |
Correct |
3 ms |
5836 KB |
Output is correct |
5 |
Correct |
3 ms |
5836 KB |
Output is correct |
6 |
Correct |
3 ms |
5836 KB |
Output is correct |
7 |
Correct |
4 ms |
5836 KB |
Output is correct |
8 |
Correct |
3 ms |
5836 KB |
Output is correct |
9 |
Correct |
3 ms |
5836 KB |
Output is correct |
10 |
Correct |
4 ms |
5836 KB |
Output is correct |
11 |
Correct |
3 ms |
5836 KB |
Output is correct |
12 |
Correct |
3 ms |
5964 KB |
Output is correct |
13 |
Correct |
4 ms |
5964 KB |
Output is correct |
14 |
Correct |
5 ms |
5956 KB |
Output is correct |
15 |
Correct |
3 ms |
5964 KB |
Output is correct |
16 |
Correct |
4 ms |
5964 KB |
Output is correct |
17 |
Correct |
4 ms |
5964 KB |
Output is correct |
18 |
Correct |
5 ms |
5964 KB |
Output is correct |
19 |
Correct |
20 ms |
6732 KB |
Output is correct |
20 |
Correct |
22 ms |
6848 KB |
Output is correct |
21 |
Correct |
25 ms |
6988 KB |
Output is correct |
22 |
Correct |
22 ms |
7156 KB |
Output is correct |
23 |
Correct |
43 ms |
10264 KB |
Output is correct |
24 |
Correct |
60 ms |
11452 KB |
Output is correct |
25 |
Correct |
66 ms |
12020 KB |
Output is correct |
26 |
Correct |
73 ms |
13000 KB |
Output is correct |
27 |
Correct |
3 ms |
5836 KB |
Output is correct |
28 |
Correct |
3 ms |
5856 KB |
Output is correct |
29 |
Correct |
4 ms |
5836 KB |
Output is correct |
30 |
Correct |
12 ms |
5836 KB |
Output is correct |
31 |
Correct |
49 ms |
6188 KB |
Output is correct |
32 |
Correct |
3 ms |
5836 KB |
Output is correct |
33 |
Correct |
3 ms |
5964 KB |
Output is correct |
34 |
Correct |
4 ms |
5964 KB |
Output is correct |
35 |
Correct |
5 ms |
5856 KB |
Output is correct |
36 |
Correct |
21 ms |
5996 KB |
Output is correct |
37 |
Correct |
80 ms |
6392 KB |
Output is correct |
38 |
Correct |
8 ms |
6860 KB |
Output is correct |
39 |
Correct |
8 ms |
6928 KB |
Output is correct |
40 |
Correct |
11 ms |
6988 KB |
Output is correct |
41 |
Correct |
30 ms |
6976 KB |
Output is correct |
42 |
Correct |
116 ms |
7396 KB |
Output is correct |
43 |
Correct |
158 ms |
27300 KB |
Output is correct |
44 |
Correct |
129 ms |
27320 KB |
Output is correct |
45 |
Correct |
141 ms |
27380 KB |
Output is correct |
46 |
Correct |
167 ms |
27456 KB |
Output is correct |
47 |
Correct |
268 ms |
28036 KB |
Output is correct |
48 |
Correct |
10 ms |
6860 KB |
Output is correct |
49 |
Correct |
29 ms |
6988 KB |
Output is correct |
50 |
Correct |
112 ms |
7108 KB |
Output is correct |
51 |
Correct |
221 ms |
7468 KB |
Output is correct |
52 |
Correct |
63 ms |
19144 KB |
Output is correct |
53 |
Correct |
93 ms |
19212 KB |
Output is correct |
54 |
Correct |
268 ms |
19400 KB |
Output is correct |
55 |
Correct |
536 ms |
19848 KB |
Output is correct |
56 |
Correct |
361 ms |
84492 KB |
Output is correct |
57 |
Correct |
401 ms |
84704 KB |
Output is correct |
58 |
Correct |
670 ms |
84828 KB |
Output is correct |
59 |
Correct |
1130 ms |
85128 KB |
Output is correct |
60 |
Correct |
768 ms |
173800 KB |
Output is correct |
61 |
Correct |
839 ms |
173780 KB |
Output is correct |
62 |
Correct |
1162 ms |
173964 KB |
Output is correct |
63 |
Correct |
1642 ms |
174384 KB |
Output is correct |
64 |
Correct |
2180 ms |
174232 KB |
Output is correct |
65 |
Correct |
3027 ms |
139044 KB |
Output is correct |
66 |
Correct |
3079 ms |
143408 KB |
Output is correct |
67 |
Correct |
3032 ms |
141108 KB |
Output is correct |
68 |
Correct |
3205 ms |
143828 KB |
Output is correct |
69 |
Correct |
3021 ms |
135208 KB |
Output is correct |
70 |
Correct |
2231 ms |
99608 KB |
Output is correct |
71 |
Correct |
4459 ms |
178332 KB |
Output is correct |
72 |
Correct |
4458 ms |
182324 KB |
Output is correct |
73 |
Correct |
4374 ms |
182448 KB |
Output is correct |
74 |
Correct |
4245 ms |
181764 KB |
Output is correct |
75 |
Correct |
3857 ms |
172764 KB |
Output is correct |
76 |
Correct |
3051 ms |
123728 KB |
Output is correct |
77 |
Correct |
4062 ms |
197220 KB |
Output is correct |
78 |
Correct |
4334 ms |
197240 KB |
Output is correct |
79 |
Correct |
4109 ms |
197224 KB |
Output is correct |
80 |
Correct |
4075 ms |
196488 KB |
Output is correct |
81 |
Correct |
3993 ms |
186352 KB |
Output is correct |
82 |
Correct |
3292 ms |
129656 KB |
Output is correct |
83 |
Correct |
4413 ms |
197172 KB |
Output is correct |
84 |
Correct |
4290 ms |
197188 KB |
Output is correct |
85 |
Correct |
4210 ms |
197400 KB |
Output is correct |
86 |
Correct |
4270 ms |
196440 KB |
Output is correct |
87 |
Correct |
4070 ms |
186228 KB |
Output is correct |
88 |
Correct |
3073 ms |
129668 KB |
Output is correct |
89 |
Correct |
2964 ms |
144888 KB |
Output is correct |
90 |
Correct |
3438 ms |
160236 KB |
Output is correct |
91 |
Correct |
3928 ms |
177008 KB |
Output is correct |
92 |
Correct |
4061 ms |
181544 KB |
Output is correct |
93 |
Correct |
4368 ms |
187392 KB |
Output is correct |
94 |
Correct |
4331 ms |
191184 KB |
Output is correct |
95 |
Correct |
4108 ms |
196568 KB |
Output is correct |
96 |
Correct |
4254 ms |
196476 KB |
Output is correct |
97 |
Correct |
4447 ms |
196656 KB |
Output is correct |
98 |
Correct |
4314 ms |
196496 KB |
Output is correct |
99 |
Correct |
4203 ms |
196544 KB |
Output is correct |
100 |
Correct |
4253 ms |
196604 KB |
Output is correct |