搜 索

Link_Cut_Tree

  • 404阅读
  • 2021年10月19日
  • 0评论
首页 / 正文

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$ 上看来可能长这样

<img src="https://cdn.jsdelivr.net/gh/moyujiang/piccdn@6804ae71482a34ff9eee5f689ab89e9a7c55edb5/2021/10/18/b6e3fbed04379cb1880565e80e4ef732.png" style="zoom:80%;" /

其中每一个圈起来的都是一颗 $\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;
}


评论区
暂无评论
avatar