CF1192B Dynamic Diameter解题报告

解题报告

CF1192B Dynamic Diameter解题报告：

更好的阅读体验

题意

• 给定一颗$n$个点的树，每条边有一个权值；
• $q$次操作，每次操作修改一条边的权值，并询问当前树的直径；
• 强制在线；
• 数据范围：$1\leqslant n,q\leqslant 10^5$。

分析

欧拉序+线段树维护好题。

对于一个直径$(x,y)$，我们可以把它拆成两条链$(x,lca(x,y))$和$(lca(x,y),y)$，此时，我们要引入一个叫欧拉序的东西：

欧拉序与dfs序很类似，对于每个结点，在进入这个结点子树时记录一遍欧拉序，每一次从儿子子树中出来时也记录一遍欧拉序。

下面给出记录欧拉序的代码：

void dfs(int x,int last){
    q[++qs]=x,in[x]=qs;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
        q[++qs]=x;
    }
    out[x]=qs;
}

其中$q$为欧拉序组成的序列，$in_x$为进入$x$子树时的欧拉序，$out_x$则为出$x$子树时的欧拉序。

这种序列有什么性质呢？

• 序列长度为$2n-1$：这个很显然，我们观察到每一条边会贡献两遍欧拉序，再加上进入根结点贡献一次欧拉序，总次数为$2(n-1)+1=2n-1$。
• 对于两个结点$x$和$y$的$lca$，它一定会在$in_x$和$in_y$中间记录一遍欧拉序，且它是$in_x$到$in_y$区间内记录了欧拉序的深度最小结点：这也很显然，因为在遍历$x$到遍历$y$的过程中，一定不会出$lca$的子树，因此没有比$lca$深度还小的子树。
• 一个子树中所有点贡献的欧拉序一定是一段连续的区间：由dfs顺序便可得这一点。

有了这个欧拉序，我们就相当于把这个树拍平了（类似于dfs序），我们来看这两个操作：

• 修改操作：$(x,y)$的边权赋值可以转化为一个加法，设在$\text{dfs}$中$x$是$y$的父亲（否则可以交换$x,y$），那么我们对$y$子树内所有点的深度进行加法就好了，在序列上就直接进行线段树区间加操作。
• 查询操作：考虑把直径的计算方法$dep_x+dep_y-2dep_{lca}$，如何在线段树上维护这个东西呢？我们把它分成两部分：$(dep_x-2dep_{lca})+dep_y$（可以交换顺序），然后再维护一些值就好了。

维护直径具体操作：

维护当前区间的最大深度$maxd_x$，最小深度$mind_x$；维护一个深度差$lm_x$，表示左边是深度深的点$x$，右边是深度浅的点$y$，它们的$dep_x-2dep_y$最大是多少，同理维护一个深度差$mr_x$，表示左边是深度浅的点$y$，右边是深度深的点$x$，它们的$dep_x-2dep_y$最大是多少，这两个东西可以很轻松的完成维护。

然后，我们维护一个路径长度$lmr_x$，代表左边一个深度深的点，中间一个深度浅的点（$lca$），右边一个深度深的点，它们的路径长度最长是多少。这个$lmr_x$可以继承左右区间的$lmr_x$，也可以用左区间的$lm_x$和右区间的$maxd_x$来合并，或者用左区间的$maxd_x$和右区间的$mr_x$合并。

维护上述值的代码：

inline void pushup(int now){
    maxd[now]=max(maxd[lc[now]],maxd[rc[now]]);
    mind[now]=min(mind[lc[now]],mind[rc[now]]);
    lm[now]=max(max(lm[lc[now]],lm[rc[now]]),maxd[lc[now]]-2*mind[rc[now]]);
    mr[now]=max(max(mr[lc[now]],mr[rc[now]]),maxd[rc[now]]-2*mind[lc[now]]);
    lmr[now]=max(max(lmr[lc[now]],lmr[rc[now]]),max(lm[lc[now]]+maxd[rc[now]],maxd[lc[now]]+mr[rc[now]]));
}

代码

边权很大，记得开$\text{long long}$。

完整代码：

#include<stdio.h>
#define int long long
const int maxn=100005;
int n,m,w,qs,e,lastans;
int start[maxn],to[maxn<<1],then[maxn<<1],worth[maxn<<1],id[maxn<<1],dis[maxn],in[maxn],out[maxn],q[maxn<<1],tid[maxn],val[maxn],maxd[maxn<<3],mind[maxn<<3],lm[maxn<<3],mr[maxn<<3],lmr[maxn<<3],lc[maxn<<3],rc[maxn<<3],lazy[maxn<<3];
inline int max(int a,int b){
    return a>b? a:b;
}
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int i){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z,id[e]=i;
}
void dfs(int x,int last){
    q[++qs]=x,in[x]=qs;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dis[y]=dis[x]+worth[i];
        tid[id[i]]=y;
        dfs(y,x);
        q[++qs]=x;
    }
    out[x]=qs;
}
inline void pushup(int now){
    maxd[now]=max(maxd[lc[now]],maxd[rc[now]]);
    mind[now]=min(mind[lc[now]],mind[rc[now]]);
    lm[now]=max(max(lm[lc[now]],lm[rc[now]]),maxd[lc[now]]-2*mind[rc[now]]);
    mr[now]=max(max(mr[lc[now]],mr[rc[now]]),maxd[rc[now]]-2*mind[lc[now]]);
    lmr[now]=max(max(lmr[lc[now]],lmr[rc[now]]),max(lm[lc[now]]+maxd[rc[now]],maxd[lc[now]]+mr[rc[now]]));
}
inline void getlazy(int now,int v){
    maxd[now]+=v,mind[now]+=v;
    lm[now]-=v,mr[now]-=v;
    lazy[now]+=v;
}
inline void pushdown(int now){
    if(lazy[now]==0)
        return ;
    getlazy(lc[now],lazy[now]),getlazy(rc[now],lazy[now]);
    lazy[now]=0;
}
void build(int l,int r,int now){
    if(l==r){
        getlazy(now,dis[q[l]]);
        return ;
    }
    int mid=(l+r)>>1;
    lc[now]=now<<1,rc[now]=now<<1|1;
    build(l,mid,lc[now]),build(mid+1,r,rc[now]);
    pushup(now);
}
void update(int l,int r,int now,int L,int R,int v){
    if(L<=l&&r<=R){
        getlazy(now,v);
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(L<=mid)
        update(l,mid,lc[now],L,R,v);
    if(mid<R)
        update(mid+1,r,rc[now],L,R,v);
    pushup(now);
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&w);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z,i),add(y,x,z,i);
        val[i]=z;
    }
    dfs(1,0);
    build(1,qs,1);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        x=(x+lastans)%(n-1)+1,y=(y+lastans)%w;
        update(1,qs,1,in[tid[x]],out[tid[x]],y-val[x]);
        val[x]=y,lastans=lmr[1];
        printf("%lld\n",lastans);
    }
    return 0;
}