#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
int INF = numeric_limits<int>::max()/4;
struct Value{
int ma = -INF;
int ma2 = -INF;
Value(){}
Value(int a){
ma = a;
}
Value(int a, int b){
ma = a;
ma2 = b;
}
void add(int v){
ma += v;
ma2 += v;
}
};
Value comb(Value a, Value b){
vector<int> r = {a.ma,a.ma2,b.ma,b.ma2};
sort(r.rbegin(),r.rend());
return Value(r[0],r[1]);
}
struct SegmentTree{
vector<Value> S;
vector<int> lazy;
int len = 1;
SegmentTree(int n){
while(len < n){
len <<= 1;
}
S.resize(2*len);
lazy.resize(2*len);
}
void upd(int i, int v){
i += len;
S[i] = Value(v);
for(i /= 2; i > 0; i /= 2){
S[i] = comb(S[i*2], S[i*2+1]);
}
}
void apply1(int i, int v){
S[i].add(v);
lazy[i] += v;
}
void push(int i){
apply1(i*2+1, lazy[i]);
apply1(i*2, lazy[i]);
lazy[i] = 0;
}
Value query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) {
return S[i];
}
if(r <= ql || qr <= l) {
return Value();
}
int mid = (l+r)/2;
push(i);
Value a = query(ql,qr,l,mid,i*2);
Value b= query(ql,qr,mid,r,i*2+1);
return comb(a,b);
}
void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) {
apply1(i,v);
return;
}
if(r <= ql || qr <= l) return;
int mid = (l+r)/2;
push(i);
apply(ql,qr,v,l,mid,i*2);apply(ql,qr,v,mid,r,i*2+1);
S[i] = comb(S[i*2], S[i*2+1]);
}
};
vector<int> val, cost;
vector<int> par, sz, depth;
vector<int> start, stop;
vector<vector<pii>> adj;
int timer = 0;
void DFS(int v, int p, int d = 0, int len = 0){
start[v] = timer++;
depth[v] = d;
sz[v] = 1;
par[v] = p;
int h = -1;
int s = -1;
for(auto u : adj[v]){
if(u.first == p) continue;
val[u.first] = len+u.second;
cost[u.first] = u.second;
DFS(u.first,v, d+1, len+u.second);
sz[v] += sz[u.first];
}
stop[v] = timer;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,q,w;
cin >> n >> q >> w;
vector<tiii> edges(n-1);
adj.resize(n);
val.resize(n);
par = sz = val = depth = cost=start=stop= vector<int>(n,-1);
for(int i = 0; i < n-1; i++){
int a,b,c;
cin >> a >> b >> c;
a--;b--;
edges[i] = {a,b,c};
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
DFS(0,0);
val[0] = 0;
cost[0] = 0;
SegmentTree seg(n);
for(int i = 0; i < n; i++){
seg.upd(i,val[i]);
}
int last = 0;
while(q--){
int d,e;
cin >> d >> e;
int edge = (last+d) % (n-1);
int weight = (e+last)%w;
int a,b,c;
tie(a,b,c) = edges[edge];
if(depth[a] < depth[b]) swap(a,b);
int diff = weight-c;
seg.apply(start[a], stop[a], diff);
edges[d] = {a,b,weight};
cost[a] = weight;
int ma = 0;
for(int i = 0; i < n; i++){
Value res = Value();
for(auto u : adj[i]){
if(u.first == par[i]) continue;
Value v = seg.query(start[u.first],stop[u.first]);
res = comb(res, Value(v.ma));
}
int rem = seg.query(start[i], start[i]+1).ma;
ma = max({ma, (res.ma+res.ma2) - (2*rem),res.ma - rem});
}
cout << ma << "\n";
last = ma;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |