题解 P3690 【【模板】Link Cut Tree （动态树）】

· · 题解

LCT模版题。

动态树是一类维护森林连通性的问题，目前最(wo)常(zhi)见(hui)的动态树就是LCT(Link-Cut-Tree),然而LCT似乎是处理路径的，处理子树可能力不足。据说有一种称为*Top Tree*的数据结构,可以处理所有。但是学不动了Orz

LCT中最主要的是Access操作，Access(u)操作的含义是，从当前的节点u向他所在的根节点连一条重路径，这是相当于把沿路的重路径全都断开，重新拉一条从u到根的重路径。

makeroot(x)操作：

若想让u成为当前树的根节点，则可以先access(u)，再splay(u)，把u转为当前splay的根节点。因为splay维护的是深度，所以u没有右儿子（没有比u还要深的点，因为重链定义），所以换根就相当于一次区间翻转，交换左右子树即完成区间翻转。此时就可以打标记了。

所以，makeroot=access+splay+rev

还有一个isroot操作，超级简单，就是判断这是不是一条重路径的根，只要他的fa指针指向的节点的左右子树都不是他（证明此时这是一条虚边），那么这就是一棵子树的根节点。

link(x,y)操作：

在u和v之间连边，可以makeroot(u)，再让u的父亲为v，这就相当于v本身是一棵splay，而u和v之间连了条轻边。

cut(u,v)操作：

断开u和v之间的边，可以先makeroot(u)，再access(v)，再splay(v)，此时v的左儿子必定为u，于是断开v和v的左儿子即可。

至于翻转标记的传递，就是跟Splay一样就行了。

但标记下放有一个问题。因为splay是时时刻刻在分裂与合并的，因为要动态维护每条重链，所以在splay之前，要先把根节点到当前节点全部下放一遍标记，防止标记下放不完全。

split(x,y)操作：

split相当于把两个子树分开，考虑到我们cut的时候第一步也是分开，所以split=makeroot(u)+access(v)+splay(v)

然后还要保存一些轻边（虚边），对于轻边我们需要单独记录处理。在原树上，当前重链的顶端节点与他的父亲的边即为轻边，如果不记录，树将是不完整的。

具体到代码实现，可以是当前splay的根节点的父亲即为当前splay上面的那个重链所在的splay上的点，但上面的splay的儿子并不指向当前splay的父亲，即为用splay的根节点的父亲来存储轻边。

动态树的主要时间消耗在Access上，而Access的时间复杂度是O(nlogn)

好像最后在UOJ群里看到一句话：

树剖能做的，动态树都能做，只不过有的东西动态树做起来比树剖烦的多

以上内容来自我的blog啦。太菜就不放link了。

#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,m,val[N];
struct Link_Cut_Tree{
    int top,c[N][2],fa[N],xr[N],q[N],rev[N];
    inline void pushup(int x){xr[x]=xr[c[x][0]]^xr[c[x][1]]^val[x];}
    inline void pushdown(int x){
        int l=c[x][0],r=c[x][1];
        if(rev[x]){
            rev[l]^=1;rev[r]^=1;rev[x]^=1;
            swap(c[x][0],c[x][1]);
        }
    }
    inline bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
    void rotate(int x){
        int y=fa[x],z=fa[y],l,r;
        if(c[y][0]==x)l=0;else l=1;r=l^1;
        if(!isroot(y)){if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;}
        fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
        c[y][l]=c[x][r];c[x][r]=y;
        pushup(y);pushup(x);
    }
    void splay(int x){
        top=1;q[top]=x;
        for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
        for(int i=top;i;i--)pushdown(q[i]);
        while(!isroot(x)){
            int y=fa[x],z=fa[y];
            if(!isroot(y)){
                if((c[y][0]==x)^(c[z][0]==y))rotate(x);
                else rotate(y);
            }rotate(x);
        }
    }
    void access(int x){for(int t=0;x;t=x,x=fa[x])splay(x),c[x][1]=t,pushup(x);}
    void makeroot(int x){access(x);splay(x);rev[x]^=1;}
    int find(int x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;}
    void split(int x,int y){makeroot(x);access(y);splay(y);}
    void cut(int x,int y){split(x,y);if(c[y][0]==x&&c[x][1]==0)c[y][0]=0,fa[x]=0;}
    void link(int x,int y){makeroot(x);fa[x]=y;}
}T;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)val[i]=read(),T.xr[i]=val[i];
    while(m--){
        int opt=read();
        if(opt==0){
            int x=read(),y=read();T.split(x,y);
            printf("%d\n",T.xr[y]);
        }
        if(opt==1){
            int x=read(),y=read(),xx=T.find(x),yy=T.find(y);
            if(xx!=yy)T.link(x,y);
        }
        if(opt==2){
            int x=read(),y=read(),xx=T.find(x),yy=T.find(y);
            if(xx==yy)T.cut(x,y);
        }
        if(opt==3){
            int x=read(),y=read();
            T.access(x);T.splay(x);val[x]=y;T.pushup(x);
        }
    }
    return 0;
}