题解 CF1192B 【Dynamic Diameter】

whiteqwq · 2020-10-13 23:14:09 · 题解

CF1192B Dynamic Diameter解题报告：

更好的阅读体验

题意

• 给定一颗n个点的树，每条边有一个权值；
• 强制在线；
• 数据范围：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]]));
}

时间复杂度：O(n\log n)。

代码

边权很大，记得开\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;
}