#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int lg = 22;
int n, q, ww, U[maxn], V[maxn], W[maxn];
vector<int> g[maxn];
int sub[maxn], block[maxn];
int tin[lg][maxn], tout[lg][maxn], timer, rtof[lg][maxn], rtlv[maxn], rtsz[maxn], nxrt[lg][maxn];
void dfssub(int u, int ant, vector<int>& verts) {
sub[u] = 1;
verts.pb(u);
for(auto i : g[u]) {
int v = u^U[i]^V[i];
int w = W[i];
if(block[v] || v == ant) continue;
dfssub(v,u,verts);
sub[u]+= sub[v];
}
}
struct {
vector<pair<int,int>> tr;
vector<int> lz;
void build(int tam) {
tr.clear();
lz.clear();
tr.resize(4*(tam+5),mp(0,0));
lz.resize(4*(tam+5),0);
}
void flush(int no, int l, int r) {
tr[no].fr+= lz[no];
if(l != r) {
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
lz[lc]+= lz[no];
lz[rc]+= lz[no];
}
lz[no] = 0;
}
void setid(int no, int l, int r, int pos, int val) {
flush(no,l,r);
if(l > pos || r < pos) return;
if(l == r) {
tr[no].sc = val;
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
setid(lc,l,mid,pos,val);
setid(rc,mid+1,r,pos,val);
tr[no] = max(tr[lc],tr[rc]);
}
void upd(int no, int l, int r, int ll, int rr, int val) {
flush(no,l,r);
if(l > rr || r < ll) return;
if(l >= ll && r <= rr) {
lz[no] = val;
flush(no,l,r);
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
upd(lc,l,mid,ll,rr,val);
upd(rc,mid+1,r,ll,rr,val);
tr[no] = max(tr[lc],tr[rc]);
}
pair<int,int> qrymax(int no, int l, int r, int ll, int rr) {
flush(no,l,r);
if(l > rr || r < ll) return mp(0,0);
if(l >= ll && r <= rr) return tr[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return max(qrymax(lc,l,mid,ll,rr),qrymax(rc,mid+1,r,ll,rr));
}
}seg[maxn];
void dfstimer(int u, int ant, int rt, int lv) {
rtof[lv][u] = rt;
tin[lv][u] = ++timer;
seg[rt].setid(1,1,rtsz[rt],tin[lv][u],u);
for(auto i : g[u]) {
int v = u^U[i]^V[i];
int w = W[i];
if(block[v] || v == ant) continue;
if(ant == -1) nxrt[lv][v] = v;
else nxrt[lv][v] = nxrt[lv][u];
dfstimer(v,u,rt,lv);
seg[rt].upd(1,1,rtsz[rt],tin[lv][v],tout[lv][v],w);
}
tout[lv][u] = timer;
}
void buildcent(int st, int lv) {
vector<int> verts;
dfssub(st,-1,verts);
int rt=-1;
for(auto u : verts) {
bool ok = true;
if(sub[st]-sub[u] > sub[st]/2) ok = false;
for(auto i : g[u]) {
int v = u^U[i]^V[i];
int w = W[i];
if(block[v] || sub[u] < sub[v]) continue;
if(sub[v] > sub[st]/2) ok = false;
}
if(ok) rt = u;
}
rtsz[rt] = sub[st];
rtlv[rt] = lv;
seg[rt].build(rtsz[rt]);
timer = 0;
dfstimer(rt,-1,rt,lv);
block[rt] = 1;
for(auto i : g[rt]) {
int v = rt^U[i]^V[i];
int w = W[i];
if(block[v]) continue;
buildcent(v,lv+1);
}
}
// max_dist,vert with max_dist
pair<int,int> query(int u) {
int lv = rtlv[u];
pair<int,int> ans = seg[u].qrymax(1,1,rtsz[u],tin[lv][u],tout[lv][u]);
while(lv--) {
int rt = rtof[lv][u];
int distme = seg[rt].qrymax(1,1,rtsz[rt],tin[lv][u],tin[lv][u]).fr;
pair<int,int> dist = max(seg[rt].qrymax(1,1,rtsz[rt],tin[lv][rt],tin[lv][nxrt[lv][u]]-1),seg[rt].qrymax(1,1,rtsz[rt],tout[lv][nxrt[lv][u]]+1,tout[lv][rt]));
ans = max(ans,mp(distme+dist.fr,dist.sc));
}
return ans;
}
void update(int u, int v, int w) {
int lv = min(rtlv[u],rtlv[v])+1;
while(lv--) {
int rt = rtof[lv][u];
if(tin[lv][u] > tin[lv][v]) swap(u,v);
seg[rt].upd(1,1,rtsz[rt],tin[lv][v],tout[lv][v],w);
}
}
void solve() {
cin >> n >> q >> ww;
for(int i = 1; i <= n-1; i++) {
cin >> U[i] >> V[i] >> W[i];
g[U[i]].pb(i);
g[V[i]].pb(i);
}
buildcent(1,0);
int last = 0;
while(q--) {
int id, neww; cin >> id >> neww;
id = (id+last)%(n-1)+1;
neww = (neww+last)%ww;
int w = neww-W[id];
W[id] = neww;
update(U[id],V[id],w);
// for(int i = 1; i <= n; i++) {block[i] = 0;}
// buildcent(1,0);
pair<int,int> d1 = query(1);
pair<int,int> d2 = query(d1.sc);
cout << d2.fr << endl;
last = d2.fr;
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
diameter.cpp: In function 'void dfssub(long long int, long long int, std::vector<long long int>&)':
diameter.cpp:27:13: warning: unused variable 'w' [-Wunused-variable]
27 | int w = W[i];
| ^
diameter.cpp: In member function 'void<unnamed struct>::flush(long long int, long long int, long long int)':
diameter.cpp:48:35: warning: unused variable 'mid' [-Wunused-variable]
48 | int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
| ^~~
diameter.cpp: In function 'void buildcent(long long int, long long int)':
diameter.cpp:123:17: warning: unused variable 'w' [-Wunused-variable]
123 | int w = W[i];
| ^
diameter.cpp:141:13: warning: unused variable 'w' [-Wunused-variable]
141 | int w = W[i];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7388 KB |
Output is correct |
2 |
Correct |
4 ms |
7508 KB |
Output is correct |
3 |
Correct |
5 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7516 KB |
Output is correct |
5 |
Correct |
4 ms |
7508 KB |
Output is correct |
6 |
Correct |
5 ms |
7460 KB |
Output is correct |
7 |
Correct |
4 ms |
7508 KB |
Output is correct |
8 |
Correct |
4 ms |
7508 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
6 ms |
7516 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
4 ms |
7640 KB |
Output is correct |
14 |
Correct |
4 ms |
7636 KB |
Output is correct |
15 |
Correct |
4 ms |
7636 KB |
Output is correct |
16 |
Correct |
4 ms |
7636 KB |
Output is correct |
17 |
Correct |
4 ms |
7636 KB |
Output is correct |
18 |
Correct |
6 ms |
7636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7388 KB |
Output is correct |
2 |
Correct |
4 ms |
7508 KB |
Output is correct |
3 |
Correct |
5 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7516 KB |
Output is correct |
5 |
Correct |
4 ms |
7508 KB |
Output is correct |
6 |
Correct |
5 ms |
7460 KB |
Output is correct |
7 |
Correct |
4 ms |
7508 KB |
Output is correct |
8 |
Correct |
4 ms |
7508 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
6 ms |
7516 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
4 ms |
7640 KB |
Output is correct |
14 |
Correct |
4 ms |
7636 KB |
Output is correct |
15 |
Correct |
4 ms |
7636 KB |
Output is correct |
16 |
Correct |
4 ms |
7636 KB |
Output is correct |
17 |
Correct |
4 ms |
7636 KB |
Output is correct |
18 |
Correct |
6 ms |
7636 KB |
Output is correct |
19 |
Correct |
20 ms |
9100 KB |
Output is correct |
20 |
Correct |
22 ms |
9164 KB |
Output is correct |
21 |
Correct |
26 ms |
9316 KB |
Output is correct |
22 |
Correct |
32 ms |
9436 KB |
Output is correct |
23 |
Correct |
47 ms |
15492 KB |
Output is correct |
24 |
Correct |
61 ms |
16864 KB |
Output is correct |
25 |
Correct |
74 ms |
17500 KB |
Output is correct |
26 |
Correct |
79 ms |
18636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7388 KB |
Output is correct |
2 |
Correct |
5 ms |
7380 KB |
Output is correct |
3 |
Correct |
6 ms |
7396 KB |
Output is correct |
4 |
Correct |
14 ms |
7648 KB |
Output is correct |
5 |
Correct |
59 ms |
8168 KB |
Output is correct |
6 |
Correct |
4 ms |
7384 KB |
Output is correct |
7 |
Correct |
4 ms |
7892 KB |
Output is correct |
8 |
Correct |
4 ms |
7764 KB |
Output is correct |
9 |
Correct |
6 ms |
7892 KB |
Output is correct |
10 |
Correct |
24 ms |
8032 KB |
Output is correct |
11 |
Correct |
72 ms |
8648 KB |
Output is correct |
12 |
Correct |
13 ms |
11748 KB |
Output is correct |
13 |
Correct |
9 ms |
11732 KB |
Output is correct |
14 |
Correct |
14 ms |
11732 KB |
Output is correct |
15 |
Correct |
33 ms |
12028 KB |
Output is correct |
16 |
Correct |
104 ms |
12580 KB |
Output is correct |
17 |
Correct |
115 ms |
92300 KB |
Output is correct |
18 |
Correct |
140 ms |
92268 KB |
Output is correct |
19 |
Correct |
117 ms |
92208 KB |
Output is correct |
20 |
Correct |
147 ms |
92320 KB |
Output is correct |
21 |
Correct |
260 ms |
92304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9172 KB |
Output is correct |
2 |
Correct |
35 ms |
9384 KB |
Output is correct |
3 |
Correct |
154 ms |
9860 KB |
Output is correct |
4 |
Correct |
357 ms |
10104 KB |
Output is correct |
5 |
Correct |
59 ms |
28108 KB |
Output is correct |
6 |
Correct |
86 ms |
28292 KB |
Output is correct |
7 |
Correct |
266 ms |
28732 KB |
Output is correct |
8 |
Correct |
560 ms |
29020 KB |
Output is correct |
9 |
Correct |
281 ms |
124396 KB |
Output is correct |
10 |
Correct |
421 ms |
124488 KB |
Output is correct |
11 |
Correct |
801 ms |
124456 KB |
Output is correct |
12 |
Correct |
1208 ms |
124804 KB |
Output is correct |
13 |
Correct |
673 ms |
253304 KB |
Output is correct |
14 |
Correct |
681 ms |
253272 KB |
Output is correct |
15 |
Correct |
1158 ms |
253204 KB |
Output is correct |
16 |
Correct |
1737 ms |
253268 KB |
Output is correct |
17 |
Correct |
2013 ms |
253240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2563 ms |
219604 KB |
Output is correct |
2 |
Correct |
2733 ms |
223304 KB |
Output is correct |
3 |
Correct |
2593 ms |
219784 KB |
Output is correct |
4 |
Correct |
2493 ms |
225264 KB |
Output is correct |
5 |
Correct |
2251 ms |
215192 KB |
Output is correct |
6 |
Correct |
1860 ms |
186908 KB |
Output is correct |
7 |
Correct |
3610 ms |
264296 KB |
Output is correct |
8 |
Correct |
3507 ms |
263532 KB |
Output is correct |
9 |
Correct |
3426 ms |
263152 KB |
Output is correct |
10 |
Correct |
3305 ms |
261544 KB |
Output is correct |
11 |
Correct |
3006 ms |
253908 KB |
Output is correct |
12 |
Correct |
2353 ms |
209936 KB |
Output is correct |
13 |
Correct |
3187 ms |
276148 KB |
Output is correct |
14 |
Correct |
3356 ms |
276180 KB |
Output is correct |
15 |
Correct |
3456 ms |
276212 KB |
Output is correct |
16 |
Correct |
3404 ms |
275280 KB |
Output is correct |
17 |
Correct |
2843 ms |
265044 KB |
Output is correct |
18 |
Correct |
2199 ms |
215644 KB |
Output is correct |
19 |
Correct |
3281 ms |
276132 KB |
Output is correct |
20 |
Correct |
3097 ms |
276116 KB |
Output is correct |
21 |
Correct |
3411 ms |
276132 KB |
Output is correct |
22 |
Correct |
3111 ms |
275332 KB |
Output is correct |
23 |
Correct |
2828 ms |
265072 KB |
Output is correct |
24 |
Correct |
2141 ms |
216108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7388 KB |
Output is correct |
2 |
Correct |
4 ms |
7508 KB |
Output is correct |
3 |
Correct |
5 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7516 KB |
Output is correct |
5 |
Correct |
4 ms |
7508 KB |
Output is correct |
6 |
Correct |
5 ms |
7460 KB |
Output is correct |
7 |
Correct |
4 ms |
7508 KB |
Output is correct |
8 |
Correct |
4 ms |
7508 KB |
Output is correct |
9 |
Correct |
5 ms |
7508 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
6 ms |
7516 KB |
Output is correct |
12 |
Correct |
5 ms |
7508 KB |
Output is correct |
13 |
Correct |
4 ms |
7640 KB |
Output is correct |
14 |
Correct |
4 ms |
7636 KB |
Output is correct |
15 |
Correct |
4 ms |
7636 KB |
Output is correct |
16 |
Correct |
4 ms |
7636 KB |
Output is correct |
17 |
Correct |
4 ms |
7636 KB |
Output is correct |
18 |
Correct |
6 ms |
7636 KB |
Output is correct |
19 |
Correct |
20 ms |
9100 KB |
Output is correct |
20 |
Correct |
22 ms |
9164 KB |
Output is correct |
21 |
Correct |
26 ms |
9316 KB |
Output is correct |
22 |
Correct |
32 ms |
9436 KB |
Output is correct |
23 |
Correct |
47 ms |
15492 KB |
Output is correct |
24 |
Correct |
61 ms |
16864 KB |
Output is correct |
25 |
Correct |
74 ms |
17500 KB |
Output is correct |
26 |
Correct |
79 ms |
18636 KB |
Output is correct |
27 |
Correct |
4 ms |
7388 KB |
Output is correct |
28 |
Correct |
5 ms |
7380 KB |
Output is correct |
29 |
Correct |
6 ms |
7396 KB |
Output is correct |
30 |
Correct |
14 ms |
7648 KB |
Output is correct |
31 |
Correct |
59 ms |
8168 KB |
Output is correct |
32 |
Correct |
4 ms |
7384 KB |
Output is correct |
33 |
Correct |
4 ms |
7892 KB |
Output is correct |
34 |
Correct |
4 ms |
7764 KB |
Output is correct |
35 |
Correct |
6 ms |
7892 KB |
Output is correct |
36 |
Correct |
24 ms |
8032 KB |
Output is correct |
37 |
Correct |
72 ms |
8648 KB |
Output is correct |
38 |
Correct |
13 ms |
11748 KB |
Output is correct |
39 |
Correct |
9 ms |
11732 KB |
Output is correct |
40 |
Correct |
14 ms |
11732 KB |
Output is correct |
41 |
Correct |
33 ms |
12028 KB |
Output is correct |
42 |
Correct |
104 ms |
12580 KB |
Output is correct |
43 |
Correct |
115 ms |
92300 KB |
Output is correct |
44 |
Correct |
140 ms |
92268 KB |
Output is correct |
45 |
Correct |
117 ms |
92208 KB |
Output is correct |
46 |
Correct |
147 ms |
92320 KB |
Output is correct |
47 |
Correct |
260 ms |
92304 KB |
Output is correct |
48 |
Correct |
9 ms |
9172 KB |
Output is correct |
49 |
Correct |
35 ms |
9384 KB |
Output is correct |
50 |
Correct |
154 ms |
9860 KB |
Output is correct |
51 |
Correct |
357 ms |
10104 KB |
Output is correct |
52 |
Correct |
59 ms |
28108 KB |
Output is correct |
53 |
Correct |
86 ms |
28292 KB |
Output is correct |
54 |
Correct |
266 ms |
28732 KB |
Output is correct |
55 |
Correct |
560 ms |
29020 KB |
Output is correct |
56 |
Correct |
281 ms |
124396 KB |
Output is correct |
57 |
Correct |
421 ms |
124488 KB |
Output is correct |
58 |
Correct |
801 ms |
124456 KB |
Output is correct |
59 |
Correct |
1208 ms |
124804 KB |
Output is correct |
60 |
Correct |
673 ms |
253304 KB |
Output is correct |
61 |
Correct |
681 ms |
253272 KB |
Output is correct |
62 |
Correct |
1158 ms |
253204 KB |
Output is correct |
63 |
Correct |
1737 ms |
253268 KB |
Output is correct |
64 |
Correct |
2013 ms |
253240 KB |
Output is correct |
65 |
Correct |
2563 ms |
219604 KB |
Output is correct |
66 |
Correct |
2733 ms |
223304 KB |
Output is correct |
67 |
Correct |
2593 ms |
219784 KB |
Output is correct |
68 |
Correct |
2493 ms |
225264 KB |
Output is correct |
69 |
Correct |
2251 ms |
215192 KB |
Output is correct |
70 |
Correct |
1860 ms |
186908 KB |
Output is correct |
71 |
Correct |
3610 ms |
264296 KB |
Output is correct |
72 |
Correct |
3507 ms |
263532 KB |
Output is correct |
73 |
Correct |
3426 ms |
263152 KB |
Output is correct |
74 |
Correct |
3305 ms |
261544 KB |
Output is correct |
75 |
Correct |
3006 ms |
253908 KB |
Output is correct |
76 |
Correct |
2353 ms |
209936 KB |
Output is correct |
77 |
Correct |
3187 ms |
276148 KB |
Output is correct |
78 |
Correct |
3356 ms |
276180 KB |
Output is correct |
79 |
Correct |
3456 ms |
276212 KB |
Output is correct |
80 |
Correct |
3404 ms |
275280 KB |
Output is correct |
81 |
Correct |
2843 ms |
265044 KB |
Output is correct |
82 |
Correct |
2199 ms |
215644 KB |
Output is correct |
83 |
Correct |
3281 ms |
276132 KB |
Output is correct |
84 |
Correct |
3097 ms |
276116 KB |
Output is correct |
85 |
Correct |
3411 ms |
276132 KB |
Output is correct |
86 |
Correct |
3111 ms |
275332 KB |
Output is correct |
87 |
Correct |
2828 ms |
265072 KB |
Output is correct |
88 |
Correct |
2141 ms |
216108 KB |
Output is correct |
89 |
Correct |
2352 ms |
219200 KB |
Output is correct |
90 |
Correct |
2649 ms |
237804 KB |
Output is correct |
91 |
Correct |
3316 ms |
256168 KB |
Output is correct |
92 |
Correct |
3278 ms |
261024 KB |
Output is correct |
93 |
Correct |
3585 ms |
267084 KB |
Output is correct |
94 |
Correct |
3596 ms |
271196 KB |
Output is correct |
95 |
Correct |
3477 ms |
275284 KB |
Output is correct |
96 |
Correct |
3471 ms |
275284 KB |
Output is correct |
97 |
Correct |
3529 ms |
277888 KB |
Output is correct |
98 |
Correct |
3369 ms |
278388 KB |
Output is correct |
99 |
Correct |
3334 ms |
277824 KB |
Output is correct |
100 |
Correct |
3191 ms |
277448 KB |
Output is correct |