C++(g++ 7.5.0) 解法, 执行用时: 283ms, 内存消耗: 48596K, 提交时间: 2022-10-11 16:51:27

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std ;

using ll = long long ;
using pii = pair<int,int> ;

// 当维护直径的时候，其实可以看作求解两个点之间距离最大值
// 那么就是 dis[u] + dis[v] - 2 * dis[lca(u,v)] ; 
// 对于欧拉序来说，这里 dis[u] + dis[v] - 2 * dis[lca(u,v)] ;
// u,v 两个点的 lca 就是欧拉序列中 dis 最小的一个
// 那么我们就可以使用线段树来进行维护
// 发现，我们维护 线段的 mx,mi,res 
// 然后为了快速求解出 res ，我们还需要维护 
// fmx = dis[u] - 2 * dis[j] (j >= u) gmx = dis[u] - 2 * dis[j] (j <= u) ;
// 然后之后的每次修改一条边，可以看作对当前的子树进行修改

const int N = 3e5 + 100 ;

int n,m ;
int h[N],e[N],ne[N],idx ;
struct Edge{
    int a,b ;
    ll c ;
}edge[N] ;
ll w[N],wmx,dis[N] ;
struct Node{
    int l,r ;
    ll mx,mi,res,fmx,gmx,add ;

    void work(ll tot){
        mx = tot,mi = tot ;
        res = 0 ;
        fmx = -tot,gmx = -tot ;
    }

}tr[N * 4] ;
int ou[N],time_stamp ;
int fi[N],se[N],dep[N] ; // 记录欧拉序第一次出现和第二次出现的位置

void add(int a,int b,ll c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}

void dfs(int u,int fa,int depth,ll distance){  // 用于求解出欧拉序
    ou[++time_stamp] = u ;
    fi[u] = time_stamp ;
    dep[u] = depth ;
    dis[u] = distance ;

    for(int i = h[u] ; ~ i ; i = ne[i]){
        int j = e[i] ;
        if(j == fa) continue ;
        dfs(j,u,depth+1,distance + w[i]) ;
        ou[++time_stamp] = u ;
    }

    se[u] = time_stamp ;
}

void pushup(int u){
    tr[u].mx = max(tr[u<<1].mx,tr[u<<1|1].mx) ;
    tr[u].mi = min(tr[u<<1].mi,tr[u<<1|1].mi) ;
    tr[u].res = max(max(tr[u<<1].res,tr[u<<1|1].res),max(tr[u<<1].fmx+tr[u<<1|1].mx,tr[u<<1|1].gmx+tr[u<<1].mx)) ;
    tr[u].fmx = max(max(tr[u<<1].fmx,tr[u<<1|1].fmx),tr[u<<1].mx - 2 * tr[u<<1|1].mi) ;
    tr[u].gmx = max(max(tr[u<<1].gmx,tr[u<<1|1].gmx),tr[u<<1|1].mx - 2 * tr[u<<1].mi) ;
}

void pushchange(int u,ll add){
    tr[u].mx += add,tr[u].mi += add ;
    tr[u].fmx -= add,tr[u].gmx -= add ;
    tr[u].add += add ;
}

void pushdown(int u){
    if(tr[u].add){
        pushchange(u<<1,tr[u].add) ;
        pushchange(u<<1|1,tr[u].add) ;
        tr[u].add = 0 ;
    }
}

void build(int u,int l,int r){
    tr[u] = {l,r} ;

    if(l == r){
        tr[u].work(dis[ou[l]]) ;
        return ;
    }

    int mid = l + r >> 1 ;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r) ;
    pushup(u) ;
}

void modify(int u,int l,int r,ll add){
    if(l <= tr[u].l &&  tr[u].r <= r){
        pushchange(u,add) ;
        return ;
    }

    pushdown(u) ;
    int mid = tr[u].l + tr[u].r >> 1 ;
    if(l <= mid) modify(u<<1,l,r,add) ;
    if(r >= mid + 1) modify(u<<1|1,l,r,add) ; 
    pushup(u) ;
}

int main(){
    scanf("%d%d%lld",&n,&m,&wmx) ; 
    memset(h,-1,sizeof h) ;
    for(int i = 1 ; i <= n - 1 ; i ++){
        scanf("%d%d%lld",&edge[i].a,&edge[i].b,&edge[i].c) ;
        add(edge[i].a,edge[i].b,edge[i].c),add(edge[i].b,edge[i].a,edge[i].c) ;
    }
    dfs(1,-1,1,0) ;
    // for(int i = 1 ; i <= 2 * n ; i ++) cout << ou[i] << " " ;

    build(1,1,2 * n) ;
    ll last = 0 ;
    while(m--){
        ll d,e ;
        scanf("%lld%lld",&d,&e) ;
        d = (d + last) % (n - 1) + 1 ;
        e = (e + last) % wmx ;
        int u ;
        if(dep[edge[d].a] > dep[edge[d].b]) u = edge[d].a ;
        else u = edge[d].b ;

        // cout << u << " " << fi[u] << " " << se[u] << "\n" ;
        modify(1,fi[u],se[u],e-edge[d].c) ;

        last = tr[1].res ;
        printf("%lld\n",last) ;

        edge[d].c = e ;
    }
    return 0 ;
}