#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct segtree { pll* max_; ll* oper; int tree_siz; void setup(int n, vi& x) { tree_siz = (1<<(__lg(n)+2))-1; max_ = new pll[tree_siz+1]; oper = new ll[tree_siz+1]; rep2(i,tree_siz/2+1,tree_siz) { if(i-(tree_siz/2+1) < siz(x)) max_[i] = {0,x[i-(tree_siz/2+1)]}; else max_[i] = {-1e9,-1}; oper[i] = 0; } for(int i = tree_siz/2; i >= 1; i--) { max_[i] = max(max_[i*2],max_[i*2+1]); oper[i] = 0; } } void push(int v) { max_[v*2].ff += oper[v]; max_[v*2+1].ff += oper[v]; oper[v*2] += oper[v]; oper[v*2+1] += oper[v]; oper[v] = 0; } void add(int akt, int p1, int p2, int s1, int s2, ll x) { if(p2 < s1 || p1 > s2) return; if(p1 >= s1 && p2 <= s2) { max_[akt].ff += x; oper[akt] += x; return; } push(akt); add(akt*2,p1,(p1+p2)/2,s1,s2,x); add(akt*2+1,(p1+p2)/2+1,p2,s1,s2,x); max_[akt] = max(max_[akt*2],max_[akt*2+1]); } pll get(int akt, int p1, int p2, int s1, int s2) { if(p2 < s1 || p1 > s2) return {-1e9,1}; if(p1 >= s1 && p2 <= s2) return max_[akt]; push(akt); return max(get(akt*2,p1,(p1+p2)/2,s1,s2),get(akt*2+1,(p1+p2)/2+1,p2,s1,s2)); } void add_seg(int l, int r, ll x) { add(1,0,tree_siz/2,l,r,x); } pll get_max(int l, int r) { if(l > r) return {-1e9,0}; return get(1,0,tree_siz/2,l,r); } }; struct centr_info { int v,s_l,s_r,l,r; }; segtree trees[100001]; vector<pii> graph[100001]; bool odw[100001]; ll cost[100001]; int sub[100001]; vector<centr_info> vert_info[100001]; vector<centr_info> edge_info[100001]; int v1=1,v2=1; int pre[100001]; int maxpre[100001]; int cur_pre = 0; vi pre_ls; void dfs_sub(int v, int pop) { sub[v] = 1; forall(it,graph[v]) { if(it.ff != pop && !odw[it.ff]) { dfs_sub(it.ff,v); sub[v] += sub[it.ff]; } } } void dfs_pre(int v, int pop) { pre_ls.pb(v); pre[v] = cur_pre++; maxpre[v] = pre[v]; forall(it,graph[v]) { if(it.ff != pop && !odw[it.ff]) { dfs_pre(it.ff,v); maxpre[v] = maxpre[it.ff]; } } } void dfs_add(int v, int pop, int centr, int s_l, int s_r) { vert_info[v].pb({centr,s_l,s_r,pre[v],maxpre[v]}); forall(it,graph[v]) { if(it.ff != pop && !odw[it.ff]) { edge_info[it.ss].pb({centr,s_l,s_r,pre[it.ff],maxpre[it.ff]}); dfs_add(it.ff,v,centr,s_l,s_r); } } } void centroid(int v, int n) { dfs_sub(v,v); int pop = v; while(true) { pii best = {0,0}; forall(it,graph[v]) { if(it.ff != pop && !odw[it.ff]) { best = max(best,{sub[it.ff],it.ff}); } } if(best.ff > n/2) { pop = v; v = best.ss; } else break; } odw[v] = 1; dfs_sub(v,v); cur_pre = 0; pre_ls = {}; dfs_pre(v,v); trees[v].setup(n,pre_ls); vert_info[v].pb({v,-1,-1,0,cur_pre-1}); forall(it,graph[v]) { if(odw[it.ff]) continue; dfs_add(it.ff,v,v,pre[it.ff],maxpre[it.ff]); edge_info[it.ss].pb({v,pre[it.ff],maxpre[it.ff],pre[it.ff],maxpre[it.ff]}); } forall(it,graph[v]) { if(!odw[it.ff]) centroid(it.ff,sub[it.ff]); } } ll query(int e, ll c, bool is = 0) { forall(it,edge_info[e]) { trees[it.v].add_seg(it.l,it.r,(!is ? -cost[e] : 0)+c); } cost[e] = c; pll ans1 = {-1,-1}; pll ans2 = {-1,-1}; forall(it,vert_info[v1]) { pll a1 = trees[it.v].get_max(0,it.s_l-1); a1.ff += trees[it.v].get_max(it.l,it.l).ff; pll a2 = trees[it.v].get_max(it.s_r+1,trees[it.v].tree_siz/2); a2.ff += trees[it.v].get_max(it.l,it.l).ff; ans1 = max({ans1,a1,a2}); } forall(it,vert_info[v2]) { pll a1 = trees[it.v].get_max(0,it.s_l-1); a1.ff += trees[it.v].get_max(it.l,it.l).ff; pll a2 = trees[it.v].get_max(it.s_r+1,trees[it.v].tree_siz/2); a2.ff += trees[it.v].get_max(it.l,it.l).ff; ans2 = max({ans2,a1,a2}); } if(ans2.ff > ans1.ff) { swap(ans1,ans2); swap(v1,v2); } v2 = ans1.ss; return ans1.ff; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,q; ll xd; cin >> n >> q >> xd; rep(i,n-1) { int a,b; cin >> a >> b >> cost[i+1]; graph[a].pb({b,i+1}); graph[b].pb({a,i+1}); } centroid(1,n); rep2(i,1,n-1) query(i,cost[i],1); ll last = 0; rep(qq,q) { int e; ll c; cin >> e >> c; e = (e+last)%(n-1); c = (c+last)%xd; last = query(e+1,c); cout << last << "\n"; } }