欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

浅谈Link-Cut Tree(LCT)

程序员文章站 2022-10-18 23:45:27
0XFF 前言&概念 Link Cut Tree 是一种用来维护动态森林连通性的数据结构，适用于动态树问题。它采用类似树链剖分的轻重边路径剖分，把树边分为实边和虚边，并用 Splay 来维护每一条实路径。 Link Cut Tree 的基本操作复杂度为均摊O(logn），但常数因子较大，一般效率会低 ......

  • 0xff 前言&概念

link-cut tree 是一种用来维护动态森林连通性的数据结构，适用于动态树问题。它采用类似树链剖分的轻重边路径剖分，把树边分为实边和虚边，并用 splay 来维护每一条实路径。link-cut tree 的基本操作复杂度为均摊o(logn），但常数因子较大，一般效率会低于树链剖分。但是却可以解决树链剖分解决不了的问题(或者优化码量) -----menci dalao

动态树lct(link cut tree)是一个可以动态维护森林上各种信息的东西(删除查找合并啥的都有吧)，原来的森林我们称为原森林，里面有实边和虚边，为啥有这两种边呢，首先lct是用很多个splay维护这个森林的信息，那么因为splay本来就是个二叉树，所以我们要将原森林”剖分”成很多个二叉树并且用splay来维护它，用实边连接起来的一棵树就是原森林中的一棵树，我们称它为原树。

这个splay会有些特殊，它的关键字是节点在树里面的深度。

这棵原树我们也不是直接用splay维护，而是按每个点在原树中的深度为优先级，将每个点以优先级的中序遍历丢到splay上。我们一般将原树所对应的splay称为辅助树，原森林就对应一个辅助树森林。
-----quhengyi11 dalao

请务必先将上文读清楚，再继续下面的阅读。

splay是辅助树，阅读时不要将主的和辅的搞混了。

显然原树中同一个深度的点是不可能在一个splay里的，因此每个splay里面就是维护了原树中的一条链

link-cut tree 准确的说是一个 splay 森林。每棵 splay 都用"虚边"链接(下图灰边表示虚边)，每棵 splay 中的结点都用"实边"链接起来(下图用黑色表示实边)。假如我们现在有一个栗子：(用红色圈圈圈在一起的结点是一个 splay 中的结点)

浅谈Link-Cut Tree(LCT)

那么现在每个结点都是一颗 splay。

就像这样：

浅谈Link-Cut Tree(LCT)

如果我们将1,2连接起来的话。

那么1,2就是同一个 splay 中的节点了。

那么现在的情况就是这样：

浅谈Link-Cut Tree(LCT)

相信你一定对此有些了解了吧。

  • 0x01 一些基本的定义

f[x]:结点x的爸爸(father)

v[x]:结点x的权值(value)

s[x]:结点x及它的子树的权值和(sum)

r[x]:结点x的翻转情况(rev)

ch[x][0/1]:结点x的左/右儿子

  • 0x02 一些操作

    link-cut tree 支持以下几种基本操作：

access(x)：将x到根节点的路径上全部变成实边，并弃掉自己所有的儿子(变成虚边：认父不认子)(每一个父结点对于自己的每个子结点只有一条实边)

findroot(x):找出x所在的原树的根结点(实际上就是上图的一号点)

makeroot(x):这个操作的意思是将x点变为原树的根节点

split(x,y):将x,y搞在一个 splay 中，以方便操作。

link(x,y):将x和y所在原树合并起来(链接)

cut(x,y):将x和y所在原树拆开(切断)

  • access(x):

    这是最基础的操作，意思是将点x到原树中根结点root之间的链丢到一个辅助树splay里面

比方说，现在森林的状态是这样的：

浅谈Link-Cut Tree(LCT)

我们的 x 现在等于6。执行 access(6) 。

那么就会将{1-3，3-6}变成实边，1-2变成虚边，假设6有一儿子n，之间用实边连着，那么这条边也将变成虚边。

每次将$x$点 splay 到当前所在辅助树的根节点，将它的右儿子更新为上一个$x$，然后令$x$跳到它的父节点，特别的，第一个$x$的右儿子设为0(null)。

q：为什么是右儿子而不是左儿子呢？

a：因为f[x]的深度小于x，而在splay里面f[x]是x的爸爸，所以x在splay中是f[x]的右儿子。

所以就变成了这样：

浅谈Link-Cut Tree(LCT)

我们将$x$旋转到辅助树的根节点，也就是将当前原树这条链上深度小于$x$(在$x$上面的点)丢到了$x$的左子树上，将$x$的右子树设为上一个$x$点相当于将$x$原来的右子树丢到了新的 splay 里面(而它们之间用虚边相连)，并且将上一段链连接起来。

现在就可以了。这棵新 splay 中只有这条链上的结点，没有其他任何的结点。如果我们指定要这三个结点同时进行操作，可以直接下传懒标记到这三个结点组成的 splay 的根结点哦!到后面splay的时候就可以直接下传跟新结点信息了。

总体过程：

浅谈Link-Cut Tree(LCT)

虚边：儿子认父，父不认子

实边：儿子认父，父也认子

用flashhu大佬的话来说，就是四步：

1.转到根。

2.换儿子。

3.更新信息。

4.当前操作点切换为轻边所指的父亲，转1。

代码实现：

inline void access(int x){
      for(register int y=0;x;y=x,x=f[x]){
            splay(x);//转到所在splay的根节点
            ch[x][1]=y;//认儿子了
            pushup(x);//儿子有变化，更新
      }
}

  • findroot(x):

  • 首先要明白：
  • 根节点是的深度最小的

我们可以通过x向上找，用 access 操作可以将x和x的根结点搞到一个 splay 里。

又因为有bst的性质：x的左子树所有结点的权值 < x < x右子树所有结点的权值。

而我们又知道，在执行完 access 操作后，这课 splay 里面的结点权值最大的(深度最大的)就是x。

于是我们可以将x splay 到这棵 splay 的根结点，那么现在最左边的节点便是这课树的根结点了。

代码实现：

inline int findroot(int x){
      access(x);//access将x和根结点搞到同一个splay中
      splay(x);//转到splay的根结点
      while(ch[x][0])pushdown(x),x=ch[x][0];//不断的找左儿子&更新节点信息
      return x;//最左边的就是根结点了。
}

  • makeroot(x):

    将x到根结点的路径上的点全部翻转(即x变成了根节点)

具体操作是我们先将x点与原树中的根打通一条链，那么现在它们就在同一棵辅助树里面了，我们发现x一定是在它所在的辅助树的中序遍历的最后一个的(因为它是这条链上最深的点)，我们把x点 splay 到辅助树的根上，那么x显然是没有右子树的，我们要实现将x移到原树的根上，也就是将x到根的这条链的深度全部翻转一遍，在辅助树上的体现就是将整棵树翻转一遍，我们可以写个翻转标记来减少复杂度。

代码实现：

inline void filp(int x){//splay普通区间翻转
      swap(ch[x][0],ch[x][1]);r[x]^=1;
} 
inline void makeroot(int x){
      access(x);
      splay(x);
      filp(x);//懒标记&翻转区间
}

  • split(x,y)

这个操作是将x到y之间的那条路径丢到一棵辅助树里，并且这棵辅助树以y节点为根(方便处理信息)。

splay 维护的是原树中的一条链，我们不能保证x,y会在同一条链里。

所以我们可以先把x变成原树的根节点(这下子access(y)就会将x到y之间的所有节点丢到一个 splay 中了)。

最后如上面所讲的，最后来一个 splay(y) 就大功告成了。

代码实现：

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

  • link(x,y):

    将x和y所在原树合并起来(链接)

首先将x点丢到原树的根，然后去找找y的根是不是x，如果不是说明x,y不在一个原树内，我们将x的父节点设为y，也就相当于从y到x连了一条虚边。

代码实现：

inline void link(int x,int y){
      makeroot(x);//丢到根
      if(findroot(y)!=x)f[x]=y;//链接一条虚边
//注意因为是虚边，所以不能认儿子
}

  • cut(x,y):

    首先我们先把x,y之间的那条边用split(x,y)拎出来，因为x,y是相邻的，所以y的左儿子一定是x，将它们的父子关系消灭掉即可。

消灭父子关系时一定满足以下条件：

1.x和y在一个原树里(不在一个树里面往哪儿切啊)

2.split之后x是y的左儿子

3.x的右儿子是空的(保证了中序遍历中y紧跟在x的后面，即深度相邻)(x的权值(深度)只比y小1，而x又正好是直接连着y的，所以我们无法再找到 >x 而又 <y 的整数了)

代码实现：

inline void cut(int x,int y){
      split(x,y);
      if(findroot(y)==x&&f[x]==y&&!ch[x][1]){//判断各种条件
            f[x]=ch[y][0]=0;//彻底切断关系
            pushup(y);//儿子变了，更新
      }return;
}

  • 0x03 splay的改动：

  • 旋转的改动：

这里需要注意一下，如果x的父亲节点的父亲节点y已经不在当前的这棵辅助树上，只需要连单向边(也就是虚边，认父不认子)，否则正常连就行，这里要和普通的rotate区分开来。

做个对比：

现在的rotate(x):

inline void rotate(int x){
      int y=f[x],z=f[y],k=chk(x),v=ch[x][!k]; 
      if(get(y))ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
      if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);
}

普通的rotate(x):

inline void rotate(int x){
      int y=f[x],z=f[y],k=chk(x),v=ch[x][!k]; 
      ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
      f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);
}

  • splay的改动

同样要注意一下只能splay到辅助树的根节点，splay之前需先下传一下这一条链上需操作的所有的点，用栈来完成即可，可以手写栈来减少常数。

inline void splay(int x){
      int y=x,top=0;hep[++top]=y;
      while(get(y))hep[++top]=y=f[y];
      while(top)pushdown(hep[top--]);

      while(get(x)){//基本普通的splay
            y=f[x],top=f[y];
            if(get(y))
                  rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
            rotate(x);
      }pushup(x);return; 
}

  • 0x04 一些题目代码：

就是上文讲的。

code:

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define a printf("a")
#define c printf(" ") 
using namespace std;
const int n=3e5+2;
template <typename tp> inline void in(tp &x){
    int f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}int f[n],v[n],s[n],r[n],hep[n],ch[n][2];
inline int get(int x){
    return ch[f[x]][0]==x||ch[f[x]][1]==x;
}
inline void pushup(int x){
    s[x]=s[ch[x][1]]^s[ch[x][0]]^v[x];
}
inline void filp(int x){
    swap(ch[x][0],ch[x][1]);r[x]^=1;
} 
inline void pushdown(int x){
    if(!r[x])return;r[x]=0;
    if(ch[x][0])filp(ch[x][0]);
    if(ch[x][1])filp(ch[x][1]);
} 
inline void rotate(int x){
    int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; 
    if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
    if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y);
}
inline void splay(int x){
    int y=x,top=0;hep[++top]=y;
    while(get(y))hep[++top]=y=f[y];
    while(top)pushdown(hep[top--]);
    while(get(x)){
        y=f[x],top=f[y];
        if(get(y))
           rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
        rotate(x);
    }pushup(x);return; 
}
inline void access(int x){
    for(register int y=0;x;x=f[y=x])
       splay(x),ch[x][1]=y,pushup(x);
}
inline void makeroot(int x){
    access(x);splay(x);filp(x);
}
inline int findroot(int x){
    access(x);splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    return x;
}
inline void split(int x,int y){
    makeroot(x);access(y);splay(y);
} 
inline void link(int x,int y){
    makeroot(x);if(findroot(y)!=x)f[x]=y;
}
inline void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
        f[x]=ch[y][0]=0;pushup(y);
    }return;
}int n,m,x,y,op;
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)scanf("%d",&v[i]); 
    for(register int i=1;i<=m;++i){
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)split(x,y),printf("%d\n",s[y]);
        else if(op==1)link(x,y);
        else if(op==2)cut(x,y);
        else splay(x),v[x]=y;
    }return 0;
}

  • [sdoi2008]洞穴勘测

分析：题目只要求link(有一条新道路==连接)和cut(道路被摧毁了==cut)以及判断连通性(直接findroot，一样的话那么就是联通的)

就是lct的板子，真的没那么难。

code:

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define a printf("a")
#define c printf(" ") 
using namespace std;
const int n=2e5+2;
template <typename tp> inline void in(tp &x){
    int f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;
}int n,m,f[n],r[n],hep[n],ch[n][2];
inline int get(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void filp(int x){swap(ch[x][0],ch[x][1]);r[x]^=1;} 
inline void pushdown(int x){
    if(!r[x])return;r[x]=0;
    if(ch[x][0])filp(ch[x][0]);
    if(ch[x][1])filp(ch[x][1]);
}
inline void rotate(int x){
    int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; 
    if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
    if(v)f[v]=y;f[y]=x,f[x]=z;return; 
}
inline void splay(int x){
    int y=x,top=0;hep[++top]=y;
    while(get(y))hep[++top]=y=f[y];
    while(top)pushdown(hep[top--]);
    while(get(x)){
        y=f[x],top=f[y];
        if(get(y))
           rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
        rotate(x);
    }return; 
}
inline void access(int x){
    for(register int y=0;x;x=f[y=x])
       splay(x),ch[x][1]=y;
}
inline void makeroot(int x){
    access(x);splay(x);filp(x);
}
inline int findroot(int x){
    access(x);splay(x);
    while(ch[x][0])pushdown(x),x=ch[x][0];
    return x;
}
inline void split(int x,int y){
    makeroot(x);access(y);splay(y);
} 
inline void link(int x,int y){
    makeroot(x);if(findroot(y)!=x)f[x]=y;
}
inline void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
        f[x]=ch[y][0]=0;
    }return;
}char op[16];
int main(){
    scanf("%d%d",&n,&m);
    for(register int x,y,i=1;i<=m;++i){
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='c')link(x,y);
        else if(op[0]=='d')cut(x,y);
        else if(op[0]=='q'){
            if(findroot(x)==findroot(y))printf("yes\n");
            else printf("no\n");
        }   
    }return 0;
}

再推存一道题目:p1501 [国家集训队]tree ii

这道题目主要就是懒标记的运用，建议在做这一道题之前先去做一做线段树的模板2，其实道理差不多，相通的，并不难。(讲乘法标记的正确下传方法弄到splay的下传上即可)

当然这道题我也附上题解：题解 p1501【[国家集训队]tree ii】(link-cut-tree)

  • 0x05 致谢：

  • 感谢flashhu大佬的文章:lct总结

  • 感谢学长quhengyi11的文章:lct学习笔记

  • 鸣谢洛谷图床，方便我上传手绘图片!

  • 最后推荐一个网址，这里面有一些基本的lct例题以及作者的解析：

上一篇： iPhone12屏幕变黄或偏黄怎么办

下一篇： PR中怎样可以修改素材帧速率？

推荐阅读