#include <bits/stdc++.h> #define int long long using namespace std; const int Nmax=1e5+5; class AINT { private: vector<int> aint; vector<int> lazy; int n; public: AINT(int siz):lazy(4*siz+5,0), aint(4*siz+5,0) { n=siz; } void propagate(int nod) { if(lazy[nod]==0) return; aint[2*nod]+=lazy[nod]; aint[2*nod+1]+=lazy[nod]; lazy[2*nod]+=lazy[nod]; lazy[2*nod+1]+=lazy[nod]; lazy[nod]=0; return; } int getmax() { return aint[1]; } void update(int nod,int l,int r,int st,int dr,int val) { if(st<=l && r<=dr) { aint[nod]+=val; lazy[nod]+=val; return; } int mid=(l+r)/2; propagate(nod); if(dr<=mid) update(2*nod,l,mid,st,dr,val); else if(mid<st) update(2*nod+1,mid+1,r,st,dr,val); else { update(2*nod,l,mid,st,mid,val); update(2*nod+1,mid+1,r,mid+1,dr,val); } aint[nod]=max(aint[2*nod],aint[2*nod+1]); } void upd(int l,int r,int val) { update(1,0,n-1,l,r,val); } }; vector<AINT> aints[Nmax]; multiset<int> bigC[Nmax]; struct edge { int u; int v; int cost; }; struct information { int tata; int l; int r; }; edge edges[Nmax]; vector<pair<int,int>> g[Nmax]; bool taken[Nmax]; int siz[Nmax],fc[Nmax],frunze[Nmax]; unordered_map<int,information> interv[Nmax]; unordered_map<int,int> nextCentroid[Nmax]; unordered_map<int,int> pozinG[Nmax]; multiset<int> allvals; void getsizes(int nod,int pr) { siz[nod]=1; for(auto [u,id]:g[nod]) { if(!taken[u] && u!=pr) { getsizes(u,nod); siz[nod]+=siz[u]; } } ///cout<<nod<<' '<<pr<<' '<<siz[nod]<<'\n'; } void getfrunze(int nod,int pr) { frunze[nod]=0; bool ok=0; for(auto [u,id]:g[nod]) { if(!taken[u] && u!=pr) { getfrunze(u,nod); frunze[nod]+=frunze[u]; ok=1; } } if(!ok) frunze[nod]++; } int getcentroid(int nod,int pr,int tot) { for(auto [u,id]:g[nod]) { if(taken[u] || u==pr) continue; if(2*siz[u]>tot) { return getcentroid(u,nod,tot); } } return nod; } void buildaint(int nod,int pr,AINT &cur,int cntfr,int cost,int tata,int centroid) { int l=cntfr,r=cntfr+frunze[nod]-1; cur.upd(l,r,cost); for(auto [u,id]:g[nod]) { if(taken[u] || u==pr) continue; buildaint(u,nod,cur,cntfr,edges[id].cost,tata,centroid); interv[id][centroid]= {tata,cntfr,cntfr+frunze[u]-1}; cntfr+=frunze[u]; } return; } int getsum(multiset<int>& s) { if(s.size()>=2) { auto it=s.rbegin(); int sum=(*it); it++; sum+=(*it); return sum; } else return (*s.rbegin()); } int decompBuild(int nod) { getsizes(nod,0); int centroid=getcentroid(nod,0,siz[nod]); getfrunze(centroid,0); int cnt=0; for(auto [u,id]:g[centroid]) { ///cout<<centroid<<' '<<u<<' '<<id<<'\n'; if(taken[u]) continue; pozinG[u][centroid]=cnt; cnt++; AINT cur(frunze[u]); ///cout<<centroid<<' '<<u<<' '<<id<<'\n'; interv[id][centroid]= {u,0,frunze[u]-1}; ///cout<<centroid<<' '<<u<<' '<<id<<'\n'; buildaint(u,centroid,cur,0,edges[id].cost,u,centroid); ///cout<<centroid<<' '<<u<<' '<<id<<' '<<cur.getmax()<<'\n'; bigC[centroid].insert(cur.getmax()); aints[centroid].push_back(cur); ///cout<<centroid<<' '<<u<<' '<<id<<'\n'; } if(!bigC[centroid].empty()) allvals.insert(getsum(bigC[centroid])); taken[centroid]=1; for(auto [u,id]:g[centroid]) { if(taken[u]) continue; nextCentroid[u][centroid]=decompBuild(u); } return centroid; } void update(int centroid,int id,int prv,int val) { ///cout<<centroid<<' '<<id<<' '<<prv<<' '<<val<<'\n'; auto [tata,l,r]=interv[id][centroid]; if(!bigC[centroid].empty()) { int poz=pozinG[tata][centroid]; int cur=aints[centroid][poz].getmax(); int curval=getsum(bigC[centroid]); ///cout<<curval<<'\n'; allvals.erase(allvals.find(curval)); bigC[centroid].erase(bigC[centroid].find(cur)); ///cout<<l<<' '<<r<<'\n'; aints[centroid][poz].upd(l,r,-prv); aints[centroid][poz].upd(l,r,val); int nw=aints[centroid][poz].getmax(); bigC[centroid].insert(nw); ///cout<<centroid<<' '<<getsum(bigC[centroid])<<' '<<"UPDATE CENTROID"<<'\n'; allvals.insert(getsum(bigC[centroid])); } if(edges[id].u==centroid && edges[id].v==tata) return; if(edges[id].u==tata && edges[id].v==centroid) return; int nxt=nextCentroid[tata][centroid]; if(nxt!=0) update(nxt,id,prv,val); return; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n,q,w; cin>>n>>q>>w; for(int i=1; i<n; i++) { cin>>edges[i].u>>edges[i].v>>edges[i].cost; g[edges[i].u].push_back({edges[i].v,i}); g[edges[i].v].push_back({edges[i].u,i}); } int firstCentroid=decompBuild(1); int last=0; ///cout<<111<<'\n'; while(q--) { int d,e; cin>>d>>e; d=(d+last)%(n-1); e=(e+last)%w; d++; ///cout<<d<<' '<<e<<'\n'; update(firstCentroid,d,edges[d].cost,e); edges[d].cost=e; last=(*allvals.rbegin()); cout<<last<<'\n'; } return 0; }