monkey.cpp

#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
typedef long long ll;
const int MM = 1e5+5, MN = 18;

#define lc (rt<<1)
#define rc (rt<<1|1)
#define nm ((nl+nr)>>1)

int first[MN][MM*2], last[MN][MM*2], ptr[MN];
//euler tour

struct st{
    ll val, lp;
} seg[MN][MM*2*3];
//stores max dis to cent

int par[MN][MM], centid[MN][MM];
//which is highest ancestor before current-level centroid, which centroid
int dep[MN][MM];
//depth to know which edge to update

int centlvl[MM];
//level of centroid

ll bestv[MM*3];
// segtree for best path going through [i] as centroid

set<pair<ll, int>, greater<pair<ll, int>>> best[MM];
//len, id

int n, q, sz[MM], tot;
ll w;
bool vis[MM];
struct edge{
    int a, b;
    ll c;
} in[MM];
vector<pair<int, ll>> adj[MM];


void build(int lvl, int nl = 1, int nr = 2*MM-1, int rt = 1){
    if(nl == nr)
        return;
    build(lvl, nl, nm, lc);
    build(lvl, nm+1, nr, rc);
    seg[lvl][rt].val = max(seg[lvl][lc].val, seg[lvl][rc].val);
}

inline void push_down(int lvl, int rt, int nl, int nr){
    ll &val = seg[lvl][rt].lp;
    if(val && nl^nr){
        seg[lvl][lc].lp += val;
        seg[lvl][lc].val += val;
        seg[lvl][rc].lp += val;
        seg[lvl][rc].val += val;
    }
    val = 0;
}

void update(int lvl, int l, int r, ll v, int nl = 1, int nr = 2*MM-1, int rt = 1){
    if(r < nl || l > nr)
        return;
    if(l <= nl && r >= nr){
        seg[lvl][rt].val += v;
        seg[lvl][rt].lp += v;
        return;
    }
    push_down(lvl, rt, nl, nr);
    update(lvl, l, r, v, nl, nm, lc);
    update(lvl, l, r, v, nm+1, nr, rc);
    
    seg[lvl][rt].val = max(seg[lvl][lc].val, seg[lvl][rc].val);
}

ll query(int lvl, int l, int r, int nl = 1, int nr = 2*MM-1, int rt = 1){
    if(r < nl || l > nr)
        return 0;
    if(l <= nl && r >= nr)
        return seg[lvl][rt].val;
    
    push_down(lvl, rt, nl, nr);
    
    return max(query(lvl, l, r, nl, nm, lc), query(lvl, l, r, nm+1, nr, rc));
}

int getsz(int cur, int pre){
    sz[cur] = 1;
    for(auto e: adj[cur]){
        int u = e.first;
        if(u != pre && !vis[u])
            sz[cur] += getsz(u, cur);
    }
    return sz[cur];
}

int findcent(int cur, int pre){
    for(auto e: adj[cur]){
        int u = e.first;
        if(!vis[u] && u != pre && sz[u]*2 > tot)
            return findcent(u, cur);
    }
    return cur;
}

void dfs(int cur, int pre, int cent, int lvl, ll pree){
    
    dep[lvl][cur] = dep[lvl][pre]+1;
    par[lvl][cur] = (pre == cent) ? cur : par[lvl][pre];
    centid[lvl][cur] = cent;
    first[lvl][cur] = ++ptr[lvl];
    
    update(lvl, ptr[lvl], n*2, pree);
    
    for(auto e: adj[cur]){
        if(!vis[e.first] && e.first != pre){
            dfs(e.first, cur, cent, lvl, e.second);
        }
    }
    
    last[lvl][cur] = ++ptr[lvl];
    update(lvl, ptr[lvl], n*2, -pree);
}

void go(int lvl, int root, int pre){
    
    getsz(root, -1);
    tot = sz[root];
    if(tot == 1){
        centlvl[root] = -1;
        return;
    }
    
    int cent = findcent(root, -1);
    vis[cent] = 1;
    centlvl[cent] = lvl;
    
    //printf("go "); print(lvl, cent);
    
    dfs(cent, 0, cent, lvl, 0);
    
    for(auto e: adj[cent]){
        if(!vis[e.first])
            go(lvl+1, e.first, cent);
    }
}


void up2(int l, ll v, int nl = 1, int nr = n, int rt = 1){
    //printf("up2 "); print(l, v, nl, nr, rt);
    if(nl == nr){
        bestv[rt] = v;
        return;
    }
    if(l <= nm)
        up2(l, v, nl, nm, lc);
    else
        up2(l, v, nm+1, nr, rc);
    
    bestv[rt] = max(bestv[lc], bestv[rc]);
}

int main(){
    
    scan(n, q, w);
    
    for(int i = 0; i < n-1; i++){
        scan(in[i].a, in[i].b, in[i].c);
        adj[in[i].a].push_back({in[i].b, in[i].c});
        adj[in[i].b].push_back({in[i].a, in[i].c});
    }
    
    go(0, 1, 0);
    
    for(int i = 0; i < MN; i++){
        build(i);
        
        for(int cent = 1; cent <= n; cent++){
            if(centlvl[cent] == i){
                for(auto e: adj[cent]){
                    int u = e.first;
                    if(centlvl[u] != -1 && centlvl[u] < i){
                        continue;
                        /*
                        print(i, cent, u, query(i, first[i][u], last[i][u]), first[i][u], last[i][u]);
                        fflush(stdout);
                        assert(query(i, first[i][u], last[i][u]) == 0);
                         */
                    }
                    ll nv = query(i, first[i][u], last[i][u]);
                    best[cent].insert({nv, u});
                }
                ll cv = 0;
                auto it = best[cent].begin();
                for(int j = 0; j < min(2, (int)best[cent].size()); j++){
                    cv += it->first;
                    it++;
                }
                up2(cent, cv);
            }
        }
    }
    /*
    for(int i = 1; i < 3*n; i++)
        printn(bestv[i]), pc(32);
    pc(10);
    */
    int ql = 0;
    
    ll pans = 0;
    while(q--){
        int d; ll e, ans = 0;
        scan(d, e);
        d = (d+pans)%(n-1);
        e = (e+pans)%w;
        
        ll dif = e-in[d].c; //reeeeeeeeee wtfffffffffffffffff
        in[d].c = e;
        
        //print(d, e, in[d].a, in[d].b);
        
        for(int i = 0; i < MN; i++){
            int a = in[d].a, b = in[d].b;
            if(dep[i][a] < dep[i][b])
                swap(a, b);
            //now a is deeper
            //print(a, b, par[i][a], par[i][b]);
            
            if(!par[i][a])
                continue;
            
            int ch = par[i][a], cent = centid[i][a];
            ll old = query(i, first[i][ch], last[i][ch]);
            //print(ch, cent, old);
            assert(*best[cent].lower_bound({old, ch}) == make_pair(old, ch));
            best[cent].erase(best[cent].lower_bound({old, ch}));
            
            update(i, first[i][a], last[i][a], dif);
            
            ll nv = query(i, first[i][ch], last[i][ch]);
            best[cent].insert({nv, ch});
            
            /*
            if(cent == 4 && ch == 6){
                printf("rep "); print(old, nv);
                printf("up "); print(first[i][a], last[i][a], dif);
            }
             */
            //rep 773 0
            
            ll cv = 0;
            auto it = best[cent].begin();
            for(int j = 0; j < min(2, (int)best[cent].size()); j++){
                //pc('a'); print(j, it->first);
                cv += it->first;
                it++;
            }
            
            up2(cent, cv);
            //print(cent, cv);
        }
        
        ans = bestv[1];
        
        print(pans = ans);
        
        /*
        printf("itr %d\n", ++ql);
        print(in[d].a, in[d].b, in[d].c);
        for(int i = 0; i < n-1; i++)
            print(in[i].a, in[i].b, in[i].c);
        
        for(int i = 1; i < 3*n; i++)
            printn(bestv[i]), pc(32);
        pc(10);
    
        for(auto i: best[4]){
            print(i.first, i.second);
        }
        puts("ok");
         */
    }
    
    return 0;
}