#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; #define int long long const int M = 1<<17, N = (1<<22) + 1; int Max[N<<1], Lz[N<<1], dead[M], ch[M], cr = 1, Ed[M], Wei[M], last; vector<pair<int, int>> nei[M], Rng[M], Top[M]; vector<int> Par[M]; multiset<int> st[M], stAns; void Push(int cur, int lc, int rc){ Max[lc] += Lz[cur], Lz[lc] += Lz[cur]; Max[rc] += Lz[cur], Lz[rc] += Lz[cur]; Lz[cur] = 0; } void Add(int l, int r, int v, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return; if (l <= st and r >= en){ Max[cur] += v, Lz[cur] += v; return; } int lc = cur<<1, rc = lc|1, mid = (st + en) >> 1; Push(cur, lc, rc); Add(l, r, v, lc, st, mid); Add(l, r, v, rc, mid, en); Max[cur] = max(Max[lc], Max[rc]); } int getMax(int l, int r, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return 0; if (l <= st and en <= r) return Max[cur]; int lc = cur<<1, rc = lc|1, mid = (st + en) >> 1; Push(cur, lc, rc); return max(getMax(l, r, lc, st, mid), getMax(l, r, rc, mid, en)); } int dfs1(int u, int p){ for (auto [i, id] : nei[u]) if (i != p and !dead[i]) ch[u] += dfs1(i, u); return ++ch[u]; } int cent(int u, int p, int rs){ for (auto [i, id] : nei[u]) if (i != p and !dead[i] and ch[i] * 2 > rs) return cent(i, u, rs); return u; } void dfs2(int u, int p, int C){ for (auto [i, id] : nei[u]){ if (i == p or dead[i]) continue; int st = cr++; Par[id].push_back(C); dfs2(i, u, C); Rng[id].push_back({st, cr}); } } void dfs3(int u, int p, pair<int, int> pr, int Id){ Top[Id].push_back(pr); for (auto [i, id] : nei[u]) if (i != p and !dead[i]) dfs3(i, u, pr, id); } void decompose(int u){ dfs1(u, u); int c = cent(u, u, ch[u]); dfs2(c, -1, c); dead[c] = 1; st[c] = {0, 0}; for (auto [i, id] : nei[c]){ if (dead[i]) continue; st[c].insert(0); dfs3(i, c, Rng[id].back(), id); } stAns.insert(0); for (auto [i, id] : nei[c]) if (!dead[i]) decompose(i); } void Upd(int id, int w){ for (int i=0;i<Par[id].size();i++){ auto [l1, r1] = Rng[id][i]; auto [l2, r2] = Top[id][i]; int C = Par[id][i]; stAns.erase(stAns.find(*rbegin(st[C]) + *next(rbegin(st[C])))); st[C].erase(st[C].find(getMax(l2, r2))); Add(l1, r1, w - Wei[id]); st[C].insert(getMax(l2, r2)); stAns.insert(*rbegin(st[C]) + *next(rbegin(st[C]))); } Wei[id] = w; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q, w; cin>>n>>q>>w; for (int i=1, a, b;i<n;i++){ cin>>a>>b>>Ed[i]; nei[a].push_back({b, i}); nei[b].push_back({a, i}); } decompose(1); for (int i=1;i<n;i++) Upd(i, Ed[i]); for (int i=1, a, b;i<=q;i++){ cin>>a>>b; a = (a + last) % (n - 1) + 1; b = (b + last) % w; Upd(a, b); last = *rbegin(stAns); cout<<last<<'\n'; } }