zcmimi's blog
查看原题

点击跳转

线段树维护动态直径

考虑设A_x为每个点的深度

答案可以写成这样的形式:

ans=\max_{1\le x<y\le n}\{ A_x + A_y - 2A_{\text{lca}(x,y)} \}

考虑欧拉序

因为边权为正,且欧拉序,那么

ans=\max_{1\le x<z<y\le n}\{ A_x + A_y - 2A_z \}

线段树维护区间内的min,max,sl,sr,s

其中min为区间最小值,max为区间最大值

sl_x=\max_{l<i<j<r} \{ A_i-2A_j \}\\ sr_x=\max_{l<i<j<r} \{ A_j-2A_i \}\\ s_x=\max_{l<i<k<j<r} \{ A_i+A_j-2A_k \}

最终答案就是s_1

修改边权可转化为子树(区间)加

#include<bits/stdc++.h>
typedef long long ll;
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
const int N=100011,M=N*2;
int n,cnt,head[N],L[N],R[N],dfn[M],sz,X[N],Y[N];ll d[N],le[M];
struct edge{int to,nxt;ll w;}e[M];
void add(int x,int y,ll w){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;e[cnt].w=w;}
void dfs(int x,int f){
    L[x]=++sz;dfn[sz]=x;
    fl(i,x)if(to!=f){
        d[to]=d[x]+e[i].w;
        dfs(to,x);
        R[x]=++sz;dfn[sz]=x;
    }
    R[x]=sz;
}
ll mi[M*4],mx[M*4],sl[M*4],sr[M*4],s[M*4],laz[M*4];
#define ls rt<<1
#define rs rt<<1|1
ll min(ll x,ll y){return x<y?x:y;}
ll max(ll x,ll y){return x>y?x:y;}
void pu(int rt){
    mi[rt]=min(mi[ls],mi[rs]);
    mx[rt]=max(mx[ls],mx[rs]);
    sl[rt]=max(max(sl[ls],sl[rs]),mx[ls]-2*mi[rs]);
    sr[rt]=max(max(sr[ls],sr[rs]),mx[rs]-2*mi[ls]);
    s[rt]=max(max(s[ls],s[rs]),max(sl[ls]+mx[rs],sr[rs]+mx[ls]));
}
void pd(int rt){
    if(laz[rt]){
        sl[ls]-=laz[rt];sr[ls]-=laz[rt];
        mi[ls]+=laz[rt];mx[ls]+=laz[rt];
        laz[ls]+=laz[rt];

        sl[rs]-=laz[rt];sr[rs]-=laz[rt];
        mi[rs]+=laz[rt];mx[rs]+=laz[rt];
        laz[rs]+=laz[rt];

        laz[rt]=0;
    }
}
void build(int l,int r,int rt){
    if(l==r)return 
        mi[rt]=mx[rt]=d[dfn[l]],
        sl[rt]=sr[rt]=-d[dfn[l]],
    void();
    int m=l+r>>1;
    build(l,m,ls);build(m+1,r,rs);
    pu(rt);
}
void upd(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R)return 
        mi[rt]+=v,mx[rt]+=v,
        sl[rt]-=v,sr[rt]-=v,
        laz[rt]+=v,
    void();
    int m=l+r>>1;
    pd(rt);
    if(L<=m)upd(L,R,v,l,m,ls);
    if(R>m)upd(L,R,v,m+1,r,rs);
    pu(rt);
}
int main(){
    int q;ll W;
    scanf("%d%d%lld",&n,&q,&W);
    int x,y,d;ll w,v,la=0;
    for(int i=1;i<n;++i){
        scanf("%d%d%lld",&x,&y,&w);
        add(x,y,w),add(y,x,w);
        X[i]=x,Y[i]=y;le[i]=w;
    }
    dfs(1,0);
    build(1,sz,1);
    while(q--){
        scanf("%d%lld",&d,&v);
        d=(d+la)%(n-1)+1;v=(v+la)%W;
        int p=(L[X[d]]>L[Y[d]]?X[d]:Y[d]);
        upd(L[p],R[p],v-le[d],1,sz,1);le[d]=v;
        printf("%lld\n",la=s[1]);
    }
}
LOJ 3163. 「CEOI2019」动态直径
comment评论
Search
search