#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int long long namespace dsa { struct segmenttreelazy { vector<ll> seg,lzy; int n; segmenttreelazy(int sz): n(sz){ seg.resize(sz*4,0); lzy.resize(sz*4,0); } void push(int l,int r,int v) { if(!lzy[v])return; seg[v]+=lzy[v]; int lc=v<<1,rc=lc|1; if(l!=r)lzy[lc]+=lzy[v],lzy[rc]+=lzy[v]; lzy[v]=0; } void update(int ql,int qr,ll vl,int l,int r,int v) { push(l,r,v); if(qr<l or r<ql)return; if(ql<=l and r<=qr) { lzy[v]+=vl; push(l,r,v); return; } int m=(l+r)>>1,lc=v<<1,rc=lc|1; update(ql,qr,vl,l,m,lc); update(ql,qr,vl,m+1,r,rc); seg[v]=max(seg[lc],seg[rc]); } void update(int ql,int qr,ll vl){update(ql,qr,vl,0,n-1,1);} ll get(int ql,int qr,int l,int r,int v) { push(l,r,v); if(qr<l or r<ql)return -1e18; if(ql<=l and r<=qr) { return seg[v]; } int m=(l+r)>>1,lc=v<<1,rc=lc|1; return max(get(ql,qr,l,m,lc),get(ql,qr,m+1,r,rc)); } ll get(int ql,int qr){return get(ql,qr,0,n-1,1);} }; struct centriod_decomposition{ vector<vector<pair<ll,int>>> ma; vector<bool> dead; vector<ll> sz,par,tour,lastwei; vector<vector<int>> anc,in,out,sub; vector<vector<vector<int>>> orient; vector<vector<ll>> wei; vector<segmenttreelazy> data; vector<multiset<ll>> mxd; multiset<ll> pos_ans; map<pair<int,int>,int> edge; int n,lim,cen,id=0,counter=0; centriod_decomposition(int un): n(un) { ma.resize(n+1,{}); anc.resize(n+1,{}); wei.resize(n+1,{}); orient.resize(n+1,{}); sub.resize(n+1,{}); in.resize(n+1,{}); out.resize(n+1,{}); dead.resize(n+1,false); sz.resize(n+1,1); par.resize(n+1,-1); lastwei.resize(n+1,0); } ll get() { return *rbegin(pos_ans); } void addedge(int x,int y,int w) { lastwei[counter]=w; edge[{x,y}]=edge[{y,x}]=counter++; ma[x].push_back({w,y}); ma[y].push_back({w,x}); } void dfs(int x,int p=0) { for(auto it:ma[x])if(it.second^p)dfs(it.second,x),sz[x]+=sz[it.second]; } int find_centriod(int x) { for(auto it:ma[x]) if(sz[it.second]>lim and !dead[it.second]) { sz[x]-=sz[it.second],sz[it.second]+=sz[x]; return find_centriod(it.second); } return x; } void euler_tour(int x,int p=0,int xas=-1) { for(auto it:ma[x]) if((it.second^p)!=0 and !dead[it.second]) { anc[it.second].push_back(id); in[it.second].push_back(tour.size()); sub[it.second].push_back(xas); tour.push_back(it.first); wei[it.second].push_back(it.first); if(xas==-1)euler_tour(it.second,x,it.second); else euler_tour(it.second,x,xas); out[it.second].push_back((int)(tour.size())-1); int ind=edge[{x,it.second}]; orient[ind].push_back({id,in[it.second].back(),out[it.second].back()}); // for(auto x:orient[ind])cout<<x<<' '; // cout<<endl; } } void add_seg(int x,int p=0,int xas=-1) { for(auto it:ma[x]) if((it.second^p)!=0 and !dead[it.second]) { int ind=edge[{x,it.second}]; if(!p)xas=it.second; orient[ind].back().push_back(in[xas].back()); orient[ind].back().push_back(out[xas].back()); data[anc[it.second].back()].update(in[it.second].back(),out[it.second].back(),it.first); add_seg(it.second,x,xas); if(!p) { // cout<<"For "<<id<<endl; // cout<<it.second<<' '<<data[anc[it.second].back()].get(in[it.second].back(),out[it.second].back())<<endl; mxd.back().insert(data[anc[it.second].back()].get(in[it.second].back(),out[it.second].back())); } } } void decompose(int x=1) { lim=sz[x]>>1; cen=find_centriod(x); dead[cen]=1; tour.clear(); euler_tour(cen); int szt=tour.size(); if(szt>0) { data.emplace_back(szt); mxd.emplace_back(); mxd.back().insert(0); mxd.back().insert(0); add_seg(cen); pos_ans.insert(*rbegin(mxd.back()) + *(++rbegin(mxd.back()))); id++; } for(auto it:ma[cen]) if(!dead[it.second]) decompose(it.second); } void update(int ed,ll nwei) { // cout<<endl<<"Main Update "<<ed<<' '<<nwei<<endl<<endl; for(auto igv:orient[ed]) { int i=igv[0]; int l=igv[3],r=igv[4]; int ul=igv[1],ur=igv[2]; pos_ans.erase(pos_ans.find(*rbegin(mxd[i]) + *(++rbegin(mxd[i])))); mxd[i].erase(mxd[i].find(data[i].get(l,r))); data[i].update(ul,ur,nwei-lastwei[ed]); mxd[i].insert(data[i].get(l,r)); pos_ans.insert(*rbegin(mxd[i]) + *(++rbegin(mxd[i]))); } lastwei[ed]=nwei; } void print() { for(int x=1;x<=n;x++) { cout<<"For "<<x<<endl; for(auto y:anc[x])cout<<y<<' '; cout<<endl; for(auto y:wei[x])cout<<y<<' '; cout<<endl; for(auto y:in[x])cout<<y<<' '; cout<<endl; for(auto y:out[x])cout<<y<<' '; cout<<endl; } } }; }; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,q,w; cin>>n>>q>>w; dsa::centriod_decomposition cd(n); for(int i=1;i<n;i++) { int a,b;ll w1; cin>>a>>b>>w1; cd.addedge(a,b,w1); } cd.dfs(1); cd.decompose(1); ll lst=0; while(q--) { ll d,e; cin>>d>>e; d=(d+lst)%(n-1); e=(e+lst)%w; cd.update(d,e); lst=cd.get(); cout<<lst<<endl; } }