#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
typedef long long ll;
typedef long long T;
constexpr int MM = 1e5+2, LOG = 17;
int n, q, tot, sz[MM], a[MM], b[MM], dep[LOG][MM], in[LOG][MM], out[LOG][MM], t[LOG], centid[LOG][MM], parid[LOG][MM];
ll maxw, c[MM];
std::vector<std::pair<int, ll>> adj[MM];
bool vis[MM];
std::multiset<ll, std::greater<ll>> best, ch[MM];
//all best, ch set for each node as centroid
struct node{
T val, lp;
inline void apply(T v){
val += v;
lp += v;
}
};
struct segtree{
#define lc (rt<<1)
#define rc (rt<<1|1)
#define nm ((nl+nr)>>1)
node tree[MM*3];
const T DEF = 0;
//default value
inline void push_up(int rt){
tree[rt].val = std::max(tree[lc].val, tree[rc].val);
}
// node with lazy val means yet to push to children (but updated itself)
inline void push_down(int rt, int nl, int nr){
T &val = tree[rt].lp;
if(nl != nr){
tree[lc].apply(val);
tree[rc].apply(val);
}
val = DEF;
}
void update(int l, int r, T val, int nl = 1, int nr = n, int rt = 1){
if(r < nl || l > nr || l > r)
return;
if(l <= nl && r >= nr){
tree[rt].apply(val);
return;
}
push_down(rt, nl, nr);
update(l, r, val, nl, nm, lc);
update(l, r, val, nm+1, nr, rc);
push_up(rt);
}
T query(int l, int r, int nl = 1, int nr = n, int rt = 1){
if(r < nl || l > nr || l > r)
return DEF;
if(l <= nl && r >= nr)
return tree[rt].val;
push_down(rt, nl, nr);
return std::max(query(l, r, nl, nm, lc), query(l, r, nm+1, nr, rc));
}
#undef lc
#undef rc
#undef nm
} ST[LOG];
int getsz(int cur, int pre){
sz[cur] = 1;
for(auto e: adj[cur]){
int u = e.first;
if(u != pre && !vis[u])
sz[cur] += getsz(u, cur);
}
return sz[cur];
}
int findcent(int cur, int pre){
for(auto e: adj[cur]){
int u = e.first;
if(!vis[u] && u != pre && sz[u]*2 > tot)
return findcent(u, cur);
}
return cur;
}
void dfs1(int cur, int pre, int lvl, int cent, ll w){
in[lvl][cur] = ++t[lvl];
dep[lvl][cur] = dep[lvl][pre]+1;
centid[lvl][cur] = cent;
parid[lvl][cur] = pre == cent ? cur : parid[lvl][pre];
for(auto u: adj[cur]){
if(u.first == pre || vis[u.first])
continue;
dfs1(u.first, cur, lvl, cent, u.second);
}
out[lvl][cur] = t[lvl];
ST[lvl].update(in[lvl][cur], out[lvl][cur], w);
}
void go(int root, int lvl){
getsz(root, -1);
tot = sz[root];
if(tot == 1)
return;
int cent = findcent(root, -1);
vis[cent] = 1;
dfs1(cent, 0, lvl, cent, 0);
for(auto u: adj[cent]){
if(vis[u.first])
continue;
int st = in[lvl][u.first], ed = out[lvl][u.first];
ll v = ST[lvl].query(st, ed);
ch[cent].insert(v);
}
while(ch[cent].size() < 2)
ch[cent].insert(0);
auto ptr = ch[cent].begin();
best.insert(*ptr + *++ptr);
for(auto u: adj[cent]){
if(!vis[u.first])
go(u.first, lvl+1);
}
}
int main(){
scan(n, q, maxw);
for(int i = 0; i < n-1; i++){
scan(a[i], b[i], c[i]);
adj[a[i]].emplace_back(b[i], c[i]);
adj[b[i]].emplace_back(a[i], c[i]);
}
go(1, 0);
ll d, e, last = 0;
while(q--){
scan(d, e);
d = (d+last)%(n-1);
e = (e+last)%maxw;
int aa = a[d], bb = b[d];
ll dif = e-c[d];
c[d] = e;
for(int i = 0; i < LOG; i++){
int cent = centid[i][aa];
if(cent and cent == centid[i][bb]){
if(dep[i][aa] < dep[i][bb])
std::swap(aa, bb);
//aa is deeper, update it
auto ptr = ch[cent].begin();
best.erase(best.lower_bound(*ptr + *++ptr));
int par = parid[i][aa];
ch[cent].erase(ch[cent].lower_bound(ST[i].query(in[i][par], out[i][par])));
ST[i].update(in[i][aa], out[i][aa], dif);
ch[cent].insert(ST[i].query(in[i][par], out[i][par]));
ptr = ch[cent].begin();
best.insert(*ptr + *++ptr);
}
}
print(last = *best.begin());
}
}
/*
* ett each centroid
* when update edge, loop through LOG levels
* if for any lvl, there is a point where centid[lvl][a] == centid[lvl][b] != 0, then update the one with higher depth
* then for its centid, remove old ans from multiset and insert new one
*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7552 KB |
Output is correct |
2 |
Correct |
9 ms |
7552 KB |
Output is correct |
3 |
Correct |
9 ms |
7552 KB |
Output is correct |
4 |
Correct |
9 ms |
7552 KB |
Output is correct |
5 |
Correct |
10 ms |
7680 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
10 ms |
7680 KB |
Output is correct |
8 |
Correct |
9 ms |
7680 KB |
Output is correct |
9 |
Correct |
9 ms |
7680 KB |
Output is correct |
10 |
Correct |
9 ms |
7680 KB |
Output is correct |
11 |
Correct |
9 ms |
7680 KB |
Output is correct |
12 |
Correct |
9 ms |
7680 KB |
Output is correct |
13 |
Correct |
9 ms |
7680 KB |
Output is correct |
14 |
Correct |
9 ms |
7680 KB |
Output is correct |
15 |
Correct |
11 ms |
7680 KB |
Output is correct |
16 |
Correct |
14 ms |
7936 KB |
Output is correct |
17 |
Correct |
10 ms |
7680 KB |
Output is correct |
18 |
Correct |
11 ms |
7808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7552 KB |
Output is correct |
2 |
Correct |
9 ms |
7552 KB |
Output is correct |
3 |
Correct |
9 ms |
7552 KB |
Output is correct |
4 |
Correct |
9 ms |
7552 KB |
Output is correct |
5 |
Correct |
10 ms |
7680 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
10 ms |
7680 KB |
Output is correct |
8 |
Correct |
9 ms |
7680 KB |
Output is correct |
9 |
Correct |
9 ms |
7680 KB |
Output is correct |
10 |
Correct |
9 ms |
7680 KB |
Output is correct |
11 |
Correct |
9 ms |
7680 KB |
Output is correct |
12 |
Correct |
9 ms |
7680 KB |
Output is correct |
13 |
Correct |
9 ms |
7680 KB |
Output is correct |
14 |
Correct |
9 ms |
7680 KB |
Output is correct |
15 |
Correct |
11 ms |
7680 KB |
Output is correct |
16 |
Correct |
14 ms |
7936 KB |
Output is correct |
17 |
Correct |
10 ms |
7680 KB |
Output is correct |
18 |
Correct |
11 ms |
7808 KB |
Output is correct |
19 |
Correct |
34 ms |
8320 KB |
Output is correct |
20 |
Correct |
37 ms |
8320 KB |
Output is correct |
21 |
Correct |
42 ms |
8448 KB |
Output is correct |
22 |
Correct |
48 ms |
8552 KB |
Output is correct |
23 |
Correct |
54 ms |
11256 KB |
Output is correct |
24 |
Correct |
71 ms |
12032 KB |
Output is correct |
25 |
Correct |
96 ms |
12536 KB |
Output is correct |
26 |
Correct |
95 ms |
13156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7552 KB |
Output is correct |
2 |
Correct |
9 ms |
7552 KB |
Output is correct |
3 |
Correct |
10 ms |
7552 KB |
Output is correct |
4 |
Correct |
19 ms |
7808 KB |
Output is correct |
5 |
Correct |
54 ms |
8312 KB |
Output is correct |
6 |
Correct |
9 ms |
7552 KB |
Output is correct |
7 |
Correct |
9 ms |
7680 KB |
Output is correct |
8 |
Correct |
10 ms |
7680 KB |
Output is correct |
9 |
Correct |
11 ms |
7680 KB |
Output is correct |
10 |
Correct |
26 ms |
8064 KB |
Output is correct |
11 |
Correct |
83 ms |
8440 KB |
Output is correct |
12 |
Correct |
13 ms |
8576 KB |
Output is correct |
13 |
Correct |
13 ms |
8576 KB |
Output is correct |
14 |
Correct |
14 ms |
8576 KB |
Output is correct |
15 |
Correct |
33 ms |
8832 KB |
Output is correct |
16 |
Correct |
116 ms |
9336 KB |
Output is correct |
17 |
Correct |
145 ms |
25212 KB |
Output is correct |
18 |
Correct |
124 ms |
25320 KB |
Output is correct |
19 |
Correct |
114 ms |
25188 KB |
Output is correct |
20 |
Correct |
146 ms |
25316 KB |
Output is correct |
21 |
Correct |
374 ms |
25804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
8320 KB |
Output is correct |
2 |
Correct |
51 ms |
8448 KB |
Output is correct |
3 |
Correct |
207 ms |
8828 KB |
Output is correct |
4 |
Correct |
398 ms |
9080 KB |
Output is correct |
5 |
Correct |
54 ms |
17272 KB |
Output is correct |
6 |
Correct |
124 ms |
17452 KB |
Output is correct |
7 |
Correct |
432 ms |
17656 KB |
Output is correct |
8 |
Correct |
871 ms |
18184 KB |
Output is correct |
9 |
Correct |
269 ms |
55800 KB |
Output is correct |
10 |
Correct |
388 ms |
55800 KB |
Output is correct |
11 |
Correct |
957 ms |
56056 KB |
Output is correct |
12 |
Correct |
1646 ms |
56312 KB |
Output is correct |
13 |
Correct |
604 ms |
109176 KB |
Output is correct |
14 |
Correct |
739 ms |
109176 KB |
Output is correct |
15 |
Correct |
1435 ms |
109744 KB |
Output is correct |
16 |
Correct |
2478 ms |
109896 KB |
Output is correct |
17 |
Correct |
4467 ms |
109812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3299 ms |
95092 KB |
Output is correct |
2 |
Correct |
3794 ms |
97812 KB |
Output is correct |
3 |
Correct |
3659 ms |
95452 KB |
Output is correct |
4 |
Correct |
3554 ms |
98104 KB |
Output is correct |
5 |
Correct |
3458 ms |
92932 KB |
Output is correct |
6 |
Correct |
3235 ms |
77276 KB |
Output is correct |
7 |
Correct |
4768 ms |
116996 KB |
Output is correct |
8 |
Correct |
4870 ms |
117036 KB |
Output is correct |
9 |
Execution timed out |
5028 ms |
116884 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7552 KB |
Output is correct |
2 |
Correct |
9 ms |
7552 KB |
Output is correct |
3 |
Correct |
9 ms |
7552 KB |
Output is correct |
4 |
Correct |
9 ms |
7552 KB |
Output is correct |
5 |
Correct |
10 ms |
7680 KB |
Output is correct |
6 |
Correct |
9 ms |
7424 KB |
Output is correct |
7 |
Correct |
10 ms |
7680 KB |
Output is correct |
8 |
Correct |
9 ms |
7680 KB |
Output is correct |
9 |
Correct |
9 ms |
7680 KB |
Output is correct |
10 |
Correct |
9 ms |
7680 KB |
Output is correct |
11 |
Correct |
9 ms |
7680 KB |
Output is correct |
12 |
Correct |
9 ms |
7680 KB |
Output is correct |
13 |
Correct |
9 ms |
7680 KB |
Output is correct |
14 |
Correct |
9 ms |
7680 KB |
Output is correct |
15 |
Correct |
11 ms |
7680 KB |
Output is correct |
16 |
Correct |
14 ms |
7936 KB |
Output is correct |
17 |
Correct |
10 ms |
7680 KB |
Output is correct |
18 |
Correct |
11 ms |
7808 KB |
Output is correct |
19 |
Correct |
34 ms |
8320 KB |
Output is correct |
20 |
Correct |
37 ms |
8320 KB |
Output is correct |
21 |
Correct |
42 ms |
8448 KB |
Output is correct |
22 |
Correct |
48 ms |
8552 KB |
Output is correct |
23 |
Correct |
54 ms |
11256 KB |
Output is correct |
24 |
Correct |
71 ms |
12032 KB |
Output is correct |
25 |
Correct |
96 ms |
12536 KB |
Output is correct |
26 |
Correct |
95 ms |
13156 KB |
Output is correct |
27 |
Correct |
10 ms |
7552 KB |
Output is correct |
28 |
Correct |
9 ms |
7552 KB |
Output is correct |
29 |
Correct |
10 ms |
7552 KB |
Output is correct |
30 |
Correct |
19 ms |
7808 KB |
Output is correct |
31 |
Correct |
54 ms |
8312 KB |
Output is correct |
32 |
Correct |
9 ms |
7552 KB |
Output is correct |
33 |
Correct |
9 ms |
7680 KB |
Output is correct |
34 |
Correct |
10 ms |
7680 KB |
Output is correct |
35 |
Correct |
11 ms |
7680 KB |
Output is correct |
36 |
Correct |
26 ms |
8064 KB |
Output is correct |
37 |
Correct |
83 ms |
8440 KB |
Output is correct |
38 |
Correct |
13 ms |
8576 KB |
Output is correct |
39 |
Correct |
13 ms |
8576 KB |
Output is correct |
40 |
Correct |
14 ms |
8576 KB |
Output is correct |
41 |
Correct |
33 ms |
8832 KB |
Output is correct |
42 |
Correct |
116 ms |
9336 KB |
Output is correct |
43 |
Correct |
145 ms |
25212 KB |
Output is correct |
44 |
Correct |
124 ms |
25320 KB |
Output is correct |
45 |
Correct |
114 ms |
25188 KB |
Output is correct |
46 |
Correct |
146 ms |
25316 KB |
Output is correct |
47 |
Correct |
374 ms |
25804 KB |
Output is correct |
48 |
Correct |
17 ms |
8320 KB |
Output is correct |
49 |
Correct |
51 ms |
8448 KB |
Output is correct |
50 |
Correct |
207 ms |
8828 KB |
Output is correct |
51 |
Correct |
398 ms |
9080 KB |
Output is correct |
52 |
Correct |
54 ms |
17272 KB |
Output is correct |
53 |
Correct |
124 ms |
17452 KB |
Output is correct |
54 |
Correct |
432 ms |
17656 KB |
Output is correct |
55 |
Correct |
871 ms |
18184 KB |
Output is correct |
56 |
Correct |
269 ms |
55800 KB |
Output is correct |
57 |
Correct |
388 ms |
55800 KB |
Output is correct |
58 |
Correct |
957 ms |
56056 KB |
Output is correct |
59 |
Correct |
1646 ms |
56312 KB |
Output is correct |
60 |
Correct |
604 ms |
109176 KB |
Output is correct |
61 |
Correct |
739 ms |
109176 KB |
Output is correct |
62 |
Correct |
1435 ms |
109744 KB |
Output is correct |
63 |
Correct |
2478 ms |
109896 KB |
Output is correct |
64 |
Correct |
4467 ms |
109812 KB |
Output is correct |
65 |
Correct |
3299 ms |
95092 KB |
Output is correct |
66 |
Correct |
3794 ms |
97812 KB |
Output is correct |
67 |
Correct |
3659 ms |
95452 KB |
Output is correct |
68 |
Correct |
3554 ms |
98104 KB |
Output is correct |
69 |
Correct |
3458 ms |
92932 KB |
Output is correct |
70 |
Correct |
3235 ms |
77276 KB |
Output is correct |
71 |
Correct |
4768 ms |
116996 KB |
Output is correct |
72 |
Correct |
4870 ms |
117036 KB |
Output is correct |
73 |
Execution timed out |
5028 ms |
116884 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |