文章	评论	标签
21	9	6

Link Cut Tree

$\text{Link Cut Tree}$，又叫动态树。正如其名，它可以支持树的分裂与合并等操作，由 $\rm RobertE.Tarjan$ 为首的科学家们提出。（没错，又是那个 $\rm Tarjan$ ）

推荐前置知识：Splay，轻重链剖分

链剖分

众所周知，维护树上信息，把他剖成链维护是很方便的。如：重链剖分，长链剖分，实链剖分

重链剖分

就是我们常说的树剖。把 $\rm size $ 最大的一个儿子当成重儿子，其余的当成轻儿子。

长链剖分

一般常用于 $\rm DP$ ，把 $\rm dep$ 最大的一个儿子当成重儿子。

实链剖分

这种剖分把儿子分为为实儿子和虚儿子。但是虚实儿子是可以随时变换的。所以我们用灵活的 $\rm Splay$ 维护一条链。也就是我们今天所要着重讨论的动态树

实现操作

access

这是 $\rm LCT$ 中最重要的操作，是一切的基础。它的作用是打通某一点到根节点的路径，让路径上全是实边。

如这一张图，红色就是实边。一条实链就用 $\rm Splay$ 维护。所以 $\rm Splay$ 上看来可能长这样

其中每一个圈起来的都是一颗 $\rm Splay$。比如现在我想打通 $12$ 到 $2$ (当前根节点)的路径，我该怎么办呢.

首先，为满足性质，我们得把 $12$ 旋转到根，然后把儿子边变成虚边（保证最深的是只能是 $12$）

怎么变成虚边呢？因为旋转到根节点后，右儿子的深度大小肯定比自己大，所以直接把右儿子设为 $0$ ，这就是常说的 认父不认子

然后把这棵 $\rm Splay$ 的根的父亲节点也旋转到他所在 $\rm Splay$ 的根，同样是将右儿子去掉，然后连上重边。比如这里需要先把 $5$ 的右儿子改成 $12$

然后把 $3$ 旋转到根节点，连上去

最后连上 $2$ 就行了

这样 $12$ 所属的 $\rm Splay$ 就是到根的路径上所有的点了

makeroot

void f(int x){tag[x]^=1;swap(ls,rs);}
void mkrt(int x){access(x);splay(x);f(x);}

首先打通到 $x$ 的点，然后把他旋转上来。因为他是深度最大的点，所以他不会有右儿子。但是因为换了跟的，所以为了深度没问题，要把左右儿子交换，并打上标记。

split

void split(int x,int y){mkrt(x);access(y);splay(y);}

作用是提出 $x,y$ 之间的路径。所以以其中一个点为根，打通另一个点的路径即可。然后把 $y$ 旋转上来，那 $y$ 所代表的信息就是整条链的信息；

find

int find(int x){access(x);splay(x);
        while(ls)push_down(x),x=ls;
        splay(x);return x;
    }

查找当前树的根（原树）。如果在同一棵树，那么 $\rm Splay$ 找到最浅的点就一定是根节点。返回就好了 , 但是路径上一定得记得下传标记

link

void link(int x,int y){mkrt(x);if(find(y)!=x)fa[x]=y;
    }

如果不在一棵树里就连边

cut

void cut(int x,int y){mkrt(x);
        if(find(y)==x&&fa[y]==x&&!c[y][0]){fa[y]=c[x][1]=0;
            push_up(x);
        }
    }

我们得保证 $x,y$ 联通，所以得用 $\rm find$ 来判断。然后我们要保证他们之间有边，所以再用后面那两个来判断。

因为可能存在 $\rm Splay$ 上， $y$ 的父亲是 $x$ ，但在原树上 $y$ 不是 $x$ 的直接儿子（由于 $\rm Splay$ 形态多变）。

Code

最后根据不同的题目，动态树也会维护不同的东西。树剖能做的 $\text{Link Cut tree}$ 基本都能做

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  a) for(int i=1,i##end=a;i<=i##end;i++)
using namespace std;
const int N=2e5+9;
inline int read(){
    int f=0,x=0;
    char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int n,m,a[N]; 
int sta[N],top;
int fa[N],c[N][2],s[N],tag[N];
struct Link_Cut_Tree{#define ls c[x][0]
    #define rs c[x][1]
    bool nrt(int x){return c[fa[x]][0]==x||c[fa[x]][1]==x;}// 判断一个点是不是根 
    void push_up(int x){s[x]=s[ls]^s[rs]^a[x];}// 更新 
    void f(int x){tag[x]^=1;swap(ls,rs);}// 翻转左右子树 
    void push_down(int x){if(!tag[x])return;f(ls);f(rs);tag[x]=0;}// 下传标记 
    void rotate(int x){// 与父亲旋转 
        int y=fa[x],z=fa[y],rel=(c[y][1]==x),w=c[x][!rel];
        if(nrt(y))c[z][c[z][1]==y]=x;c[x][!rel]=y;c[y][rel]=w;
        if(w)fa[w]=y;fa[y]=x;fa[x]=z;
        push_up(y);push_up(x);
    }
    void splay(int x){// 转到根节点 
        int now=x;
        top=0;sta[++top]=now;
        while(nrt(now))sta[++top]=now=fa[now];
        while(top)push_down(sta[top--]);
        while(nrt(x)){int y=fa[x],z=fa[y];
            if(nrt(y))rotate((c[y][1]==x)^(c[z][1]==y)?x:y);
            rotate(x);
        }
        push_up(x);
    }
    void access(int x){// 打通路径 
        for(int y=0;x;x=fa[y=x])
            splay(x),rs=y,push_up(x);
    }
    void mkrt(int x){access(x);splay(x);f(x);}// 换根 
    int find(int x){// 找在原图中的根 
        access(x);splay(x);
        while(ls)push_down(x),x=ls;
        splay(x);return x;
    }
    void split(int x,int y){mkrt(x);access(y);splay(y);}// 提出 xy 之间的路径 
    void link(int x,int y){// 连边 
        mkrt(x);if(find(y)!=x)fa[x]=y;
    }
    void cut(int x,int y){// 删边 
        mkrt(x);
        if(find(y)==x&&fa[y]==x&&!c[y][0]){fa[y]=c[x][1]=0;
            push_up(x);
        }
    }
}T;
int main(){//    printf("%.5lf",(&pppp-&ppp)/1024.0/1024.0);
    n=read(),m=read();
    rep(i,n)a[i]=read();
    while(m--){int op=read(),x=read(),y=read();
        switch(op){case 0:T.split(x,y);printf("%d\n",s[y]);break;
            case 1:T.link(x,y);break;
            case 2:T.cut(x,y);break;
            case 3:T.splay(x);a[x]=y;break; 
        }
    }
    return 0;
}

Link_Cut_Tree

华恋