首页 > 笔记 > Link-cut-tree学习总结

Link-cut-tree学习总结

Link-Cut-Tree(简称LCT)是解决动态树类问题一种数据结构。把重链用Splay表示的思想非常有趣。

LCT是由Tarjan发明的(又是他

LCT的基础是Splay,但是二者不完全相同,直接套Splay的模板是很容易出错的= =

假如我们要解决一个问题,维护一个序列,支持下列操作:

区间求和
区间求最值
区间修改
求连续子段和

直接线段树就行了

假如这个呢

维护一个序列,支持下列操作:

区间求和
区间求最值
区间修改
求连续子段和
添加一段区间
删除一段区间
翻转一段区间

那就只能用Splay了。例题:NOI2005 D1T2 维修序列

假如我们把操作都移到树上:

维护一棵树,支持下列操作:

链上求和
链上求最值
链上修改
子树修改
子树求和
换根

这就可以用树链剖分解决了

那么这个呢

维护一棵树,支持下列操作:

链上求和
链上求最值
链上修改
断开树上的一条边
连接两个点,保证连接后仍然是一棵树

这就是一个简单的动态树问题

由于树是动态的,我们不能每次操作都重标号一遍,树链剖分搞不了

然而我们可以沿用树链剖分的轻重链剖分的概念

既然是动态那么我们肯定要把静态的线段树换成动态的Splay

于是就有LCT=树链剖分+Splay

引入一些概念:

Preferred Child:重儿子(为了便于理解这里沿用树链剖分中的命名),重儿子与父亲节点同在一棵Splay中,一个节点最多只能有一个重儿子
Preferred Edge:重(zhòng)边,连接父亲节点和重儿子的边
Preferred Path:重链,由重边及重边连接的节点构成的链
Auxiliary Tree(辅助树):由一条重链上的所有节点所构成的Splay称作这条链的辅助树

 

在辅助树上,每个点的键值为这个点的深度,即这棵Splay的中序遍历是这条链从链顶到链底的所有节点构成的序列

辅助树的根节点的父亲指向链顶的父亲节点,然而链顶的父亲节点的儿子并不指向辅助树的根节点

images

原树中的重链:辅助树中两个节点位于同一棵Splay中
原树中的轻链:辅助树中子节点所在Splay的根节点的father指向父节点

注意原树与辅助树的结构并不相同

辅助树的根节点≠原树的根节点
辅助树中的father≠原树中的father

由于要维护的信息已经都在辅助树中维护了,所以LCT无需维护原树,只维护辅助树即可

轻链和重链并不是固定的,随着算法的进行,轻链和重链随算法需要和题目要求而变化,然而无论怎么变化,由这棵辅助树一定能生成原树,并满足辅助树的所有性质

 

下面就是一些操作:

Splay部分

1.is_root

int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}

它的作用就是判断一下x是否是根,因为假如它是根的话在辅助树中它的父亲的孩子就是自己。

2.pushdown

void pushdown(int x)
{
    if (res[x] && x)
    {
        if (ch[x][0]) res[ch[x][0]]^=1;
        if (ch[x][1]) res[ch[x][1]]^=1;
        swap(ch[x][1],ch[x][0]);
        res[x]=0;
    }
}

这个操作是下推反转标记,置于为什么有反转标记,下面会讲。

3.splay

int get_son(int x){return ch[f[x]][1]==x;}
void rot(int x)
{
    int fa=f[x],fafa=f[fa],k=get_son(x);
    if (!is_root(fa)) ch[fafa][ch[fafa][1]==fa]=x;
    ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa;
    ch[x][k^1]=fa,f[fa]=x;
    f[x]=fafa;
    update(fa);update(x);
}
void push(int x)
{
    if(!is_root(x)) push(f[x]);
    pushdown(x);
}
void splay(int x)
{
    push(x);
    for (int fa;!is_root(x);rot(x))
        if (!is_root(fa=f[x]))
            rot(get_son(x)==get_son(fa)?fa:x);
}

在Splay前,要把x到根上的路径pushdown。

注意第5行的部分,这个不能放到后面,要不会死循环。

因为假如你放的了后面,它的父子关系就已经改变了,不是直接判断is_root。

LCT操作

1.access

void access(int x)
{
    for (int y=0;x;y=x,x=f[x])
        splay(x),ch[x][1]=y;
}

Access(一些版本中也叫做Expose)函数,是LCT各种姿势的基础

Access函数的作用是:将一个点与原先的重儿子切断,并使这个点到根路径上的边全都变为重边

即执行Access(x)函数后这个节点到根的路径上的所有节点形成了一棵Splay

便于操作或查询节点到根路径上的所有节点

一个例子:

images

access以前的树

images

具体实现:根据辅助树按照深度为关键字的性质,重建一颗splay。不断地将一个结点的父亲转到根,然后把这个结点接到它父亲的右儿子。

2.make_root

把x换成根

void make_root(int x){access(x),splay(x),res[x]^=1;}

作用:将x设为原树的根

有向树没有这个操作

注意Access(x)之后x只是辅助树的总根,并不是原树的根,因为Access(x)之后x还有左子树,左子树的深度小于x,故x不是根节点

发现x设为根之后,原先x到根的路径上点的深度正好反转

于是只需要在Access+Splay之后翻转即可

具体实现:因为原树是虚树,所以在原树中进行变换实际上是在辅助树中进行变换。首先Access一个点,再将这个点在辅助树中转到根。又是根据辅助书按照深度为关键字的性质,将这个点所在的splay树反转,实际上改变了深度的关系,也就是实现的原树的换根。

3.find_root

int find_root(int x)
{
    access(x),splay(x);
    while(ch[x][0])
        x=ch[x][0];
    return x;
}

它可以找一个点在原树中的根,用于判断两个点的连通性。

具体实现:首先Access这个点,然后在辅助树中将这个点转到根,由于辅助树按照深度为关键字排序,所以不断地向左子树寻找,就可以找到深度最小的根。

4.link

void link(int x,int y){make_root(x),f[x]=y,splay(x);}

它可以将两个不连通的点连通。也可以说把两个树连起来。

具体实现:首先make_root,在原树中将一个点转到那个点所在的树的根。然后将这个转到根的点的father接到另外一个点上。可以进行一次splay来update。【logn不值钱

5.cut

void cut(int x,int y){make_root(x),access(y),splay(y),ch[y][0]=f[x]=0;}

将x和y之间的连边切断

直接将x make_root,然后将y进行Access+Splay,之后x一定在y的左儿子上,直接切断即可

证明:反证法

假设y进行Access+Splay操作时通过双旋将x旋转到y的左儿子的左儿子 那么x和y之间一定有一个节点 故xy之间深度之差不为1 与已知xy之间有连边相矛盾

5.对x到y路径上的点进行修改或查询

只需要对x进行make_root操作,然后对y进行Access+Splay操作,那么x到y路径上的所有点都在以y为根的子树上,之后就随便搞了

至此,我们就写完了LCT的所有操作

例题

bzoj2049

#include <cstdio>
#define N 10010
using namespace std;
#define read(a) a=getnum()
inline int getnum()
{ int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar());
for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }
int n,m,x,y,f[N],ch[N][2],siz[N],res[N];
char s[10];
void swap(int &a,int &b){int t=a;a=b;b=t;}
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
void pushdown(int x)
{
    if (res[x] && x)
    {
        if (ch[x][0]) res[ch[x][0]]^=1;
        if (ch[x][1]) res[ch[x][1]]^=1;
        swap(ch[x][1],ch[x][0]);
        res[x]=0;
    }
}
int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}
int get_son(int x){return ch[f[x]][1]==x;}
void rot(int x)
{
    int fa=f[x],fafa=f[fa],k=get_son(x);
    if (!is_root(fa))
        ch[fafa][ch[fafa][1]==fa]=x;
    ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa;
    ch[x][k^1]=fa,f[fa]=x;
    f[x]=fafa;
    update(fa);update(x);
}
void push(int x)
{
    if(!is_root(x)) push(f[x]);
    pushdown(x);
}
void splay(int x)
{
    push(x);
    for (int fa;!is_root(x);rot(x))
        if (!is_root(fa=f[x]))
            rot(get_son(x)==get_son(fa)?fa:x);
}
void access(int x)
{
    for (int y=0;x;y=x,x=f[x])
        splay(x),ch[x][1]=y;
}
int find_root(int x)
{
    access(x),splay(x);
    while(ch[x][0])
        x=ch[x][0];
    return x;
}
void make_root(int x){access(x),splay(x),res[x]^=1;}
void link(int x,int y){make_root(x),f[x]=y,splay(x);}
void cut(int x,int y){make_root(x),access(y),splay(y),ch[y][0]=f[x]=0;}
main()
{
    read(n);read(m);
    for (int i=1;i<=m;++i)
    {
        scanf("%s",s);
        read(x);read(y);
        if (s[0]=='Q')
            if (find_root(x)==find_root(y))
                printf("Yes\n");
            else
                printf("No\n");
        if (s[0]=='C')
            link(x,y);
        if (s[0]=='D')
            cut(x,y);
    }
}

The end.