P6845 题解 | 动态直径的 dfs 序做法

· · 题解

题意

给一个 n 个点边带权的树，q 次改边权，每次改完后问树上的直径。强制在线。

保证树上的边权一直是正的。

## 思路 我们可以把直径改写成下面这样的式子： $$\max_{i,j}\{d_i+d_j-2d_{lca(i,j)}\}$$ 其中 $d_i$ 表示 $i$ 到根的距离。 把树拍成 dfs 序，设 $i$ 的 dfs 序为 $p_i$，那么 $d_{lca(i,j)}$ 就是 $x\in[\min(p_i,p_j)+1,\max(p_j)]$ 中 $d_{fa_x}$ 的最小值。那么如果我们设 $a_{p_i}=d_i$，$b_{p_i}=d_{fa_i}$，那么直径就是 $$\max_{i<j\leq k}\{a_i-2b_j+a_k\}$$ 而修改边权就是对 $a$ 和 $b$ 的区间加。这样我们可以用线段树维护了。具体来说，在线段树上维护以下内容： - $\max_i\{a_i\}$，$\min_j\{b_j\}

即可完成转移。具体转移方式可以看代码。

最后需要注意，对 a 的区间加和对 b 的区间加的区间是不一样的。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct SEG{
    struct st{
        int l,r,z,a,b,ab,bc,abc;
    }a[266666];
    void bt(int x,int l,int r){
        a[x].l=l;
        a[x].r=r;
        if(l<r){
            bt(x<<1,l,(l+r>>1));
            bt(x<<1|1,(l+r>>1)+1,r); 
        }
        else a[x].ab=a[x].abc=-1e18;
    }
    void pu(int x){
        a[x].a=max(a[x<<1].a,a[x<<1|1].a);
        a[x].b=max(a[x<<1].b,a[x<<1|1].b);
        a[x].ab=max({a[x<<1].ab,a[x<<1|1].ab,a[x<<1].a+a[x<<1|1].b});
        a[x].bc=max({a[x<<1].bc,a[x<<1|1].bc,a[x<<1].b+a[x<<1|1].a});
        a[x].abc=max({a[x<<1].abc,a[x<<1|1].abc,a[x<<1].ab+a[x<<1|1].a,a[x<<1].a+a[x<<1|1].bc});
    }
    void ps(int x,int v){
        a[x].a+=v,a[x].b-=v*2;
        a[x].ab-=v,a[x].bc-=v;
        a[x].z+=v;
    }
    void xf(int x){
        ps(x<<1,a[x].z),ps(x<<1|1,a[x].z);
        a[x].z=0;
    }
    void mdf(int x,int l,int r,int v){
        if(a[x].l==l&&a[x].r==r) return ps(x,v);
        xf(x);
        int mid=a[x].l+a[x].r>>1;
        if(r<=mid) mdf(x<<1,l,r,v);
        else if(l>mid) mdf(x<<1|1,l,r,v);
        else mdf(x<<1,l,mid,v),mdf(x<<1|1,mid+1,r,v);
        pu(x); 
    }
    void cg(int x,int p,int v){
        if(a[x].l==a[x].r){
            a[x].b+=v*2;
            a[x].bc+=v*2;
            return;
        }
        xf(x);
        int mid=a[x].l+a[x].r>>1;
        cg(x<<1|(p>mid),p,v);
        pu(x);
    }
    int que(){
        return max(0ll,a[1].abc);
    }
}T;
int n,q,V,w[100005],p[100005],dfn[100005],out[100005],dcnt;
vector<pair<int,int> >e[100005];
void dfs(int x,int f){
    dfn[x]=++dcnt;
    for(auto i:e[x]){
        if(i.first==f) continue;
        dfs(i.first,x);
        p[i.second]=i.first;
    }
    out[x]=dcnt;
}
void ad(int i,int v){
    T.mdf(1,dfn[p[i]],out[p[i]],v);
    T.cg(1,dfn[p[i]],v);
}
signed main(){
    cin>>n>>q>>V;
    for(int i=1,u,v;i<n;i++){
        scanf("%lld %lld %lld",&u,&v,&w[i]);
        e[u].push_back({v,i});
        e[v].push_back({u,i});
    }
    dfs(1,0);
    T.bt(1,1,n);
    for(int i=1;i<n;i++) ad(i,w[i]);
    for(int i=1,l=0,j,k;i<=q;i++){
        scanf("%lld %lld",&j,&k);
        j=(j+l)%(n-1)+1,k=(k+l)%V;
        ad(j,k-w[j]),w[j]=k;
        printf("%lld\n",l=T.que());
    }
    return 0;
}