Link Cut Tree （动态树）简析

发表于
字数统计: 3,509 | 阅读时长 ≈ 15

前言：

我是真的菜…修锅修了好久…
所以写前言真的只是随便的并没有什么内容…
另外这篇题解可能会折腾我很久…

侵删

LCT动态树

LCT的定义

LCT是把一棵树分解成很多条树链，而每条树链用 Splay 维护，如果我们需要对一棵树的路径进行操作的时候，利用 Splay 进行分离与合并，把这条路径储存在同一棵 Splay 上，然后再进行操作这棵 Splay

LCT的概念

我们现在来看一下LCT有什么概念…

  • Preferred Child：偏好子节点
  • Preferred Edge：偏好边
  • Preferred Path：偏好路径
  • Auxiliary Tree：辅助树
  • Path Parent：路径父节点

为了加深理解，我们来看一下这样一张图

上图中节点1是树的根，1的偏好子节点是2 , 2的偏好子节点有4 ，而3,5,6 并没有偏好子节点
偏好子节点连成的边叫做偏好边
和树链剖分相似的，LCT也把树分成很多条线型的链，但是LCT采用了Splay-Tree来储存这些链

我们再来看一张图

我们把蓝色标记出的链处理成一棵 Splay ，可以发现，离根节点近的边被储存到 Splay 的左边，离根节点较远的被储存到右边，Splay-tree 是以deep 作为关键字排序的。
这样的链我们我们称之为偏好路径

储存多条树链

我们称 Splay 的根的父亲为路径父节点
如何储存这棵树，我们来看下面一张图

我们把树链当成一个点，轻边（即不是偏好边的边）当成树上的边，可以发现，我们得到的新树要比原先的树小的多，现在我们称修改后的树为虚树
如果一棵虚树的数据结构不再发生改变的话，同树链剖分，每个节点都用线型的数据结构加速的话，就能达到 log 级别的效率，我们可以把树链剖分理解成静态的LCT…
但是LCT最重要的一点是，它总能在 log 的时间级里，把需要查询的区间构造成主链，我们现在来看看如何实现

LCT的基本操作

构造主链的操作并不是只基于一种基础操作，而且LCT不仅仅只需要构造主链这种操作，我们来看看LCT有哪些基本操作

access

access操作是LCT所有操作的基础
如果我们调用access操作，那么操作完成后，根节点到节点 i 就变成了一条偏好路径，这条路径上的所有点就变成了偏好孩子。同时，这条路径变成了一棵 Splay
假设我们访问到节点 i ，先把节点 i 伸展到该树的根，再断开它的右孩子（访问到的节点是没有右孩子的…)，然后我们再访问 i 的路径父节点 x ，把节点 i 接在 x 的右节点上，不断重复该操作，最后，我们就能得到一条从根节点连到 i 的一条树链

上图是一棵虚树，假设我们需要access（2）

先旋转点 2 至所在 Splay-Tree 的根，再断开点 3 的右孩子，旋转点3 至它的根，将点 2 连接上

现在我们要访问的节点 2 已经在根为 3 的 Splay 上，来看看整棵树的形状

我们现在再旋转点 1，把点 1 的右孩子接在点 3 上，可以发现，整棵树的根 1 已经和我们访问的点 2，在同一条树链上了

看样子操作很长其实也只要写一个循环就可以了，我们来看一下

1
2
3
4
5
inline int access(int x){
    int t=0;
    while(x){splay(x);ch[x][1]=t;t=x;x=fa[x];}
    return t;
}
findroot

查找树根操作找的是原树的树根（即主链中 deep 的最小点），并不是LCT的树根

我们在access（ i ），之后，根节点是 包括 i 的辅助树中的 deep 的最小点，因此，我们只需要先把 i 旋转到它所在数的根，再从 i 开始一直往左走，最后的节点就是我们要询问的结果

我们来看一下代码实现

1
2
3
4
inline int find(int x){
    access(x);splay(x);int now=x;
    while(ch[now][0]!=0) now=ch[now][0];return now;
}
makeroot

makeroot的意思是改变原树的树根，有时候我们需要这样做来进行更多操作
我们在改变树根的时候，最好把原先的根节点和要改变成树根的节点在同一条链上，这样我们就不会牵扯到很多的树链，操作也不会变得复杂，因此，我们用access操作将我们要改变的点 i 和根 x 在存在于同一条链上
我们先来看一张图

假设我们要将根点 1 换成点 6，换完之后的样式是上图
可以发现，除去主链之外的所有链，在换根操作的时候都是不受影响的
但是红色标记的主链，是被翻转的。这意味着，我们每换一次根，在主链这棵 Splay 上都是被翻转的，这需要我们在 Splay 里的操作里用上区间翻转…
我们用上类似于线段树的延迟标记，在进行 Splay 的操作中进行释放
现在我们先来看一下代码实现

1
2
3
inline void makeroot(int x){
	access(x);splay(x);tag[x]^=1;
}

link 操作的目的是合并两棵 LCT，我们来看一下思路（以下思路基于这两棵LCT不同
如果我们要合并两个点 x 和 y ，只需要将 x makeroot 到根，再使点 x 的父亲节点为 y ，这时 x 所在的 Splay 和 y 有一条边相连，但是合并后的树并没有一个根，这时我们就需要把 y 当做新树的根，splay（y)即可(其实重新换树根也是可以的…
我们来看两张图增进理解

我们来看一下代码

1
2
3
inline void link(int x,int y){
	if(find(x)!=find(y)) makeroot(x),fa[x]=y,splay(y);
}
cut

cut 操作和 link 操作相反，它的目的是断开一棵LCT
假设我们需要断开点 x 与点 y 的边
我们先把点 x makeroot，再access( y ) ,这时 x 和 y 就在同一条链上了

假设我们要断开点 1 ，和点 5

然后我们再断开

断开操作就完成了，我们看一下代码实现，其实很短…

1
2
3
4
5
inline void cut(int x,int y){
    makeroot(x);access(y);splay(y);
    if(fa[x]!=y||!ch[y][0]) return;
    ch[y][0]=0;fa[x]=0;
}

另外的，我们需要进行特判（我就在这里卡了很久…我好菜啊
点 x 在这之后就不是树的根了，若点 x 的父亲节点不是 y 的时候，这两点已经没有边相连，我们直接返回即可
还有，一个点的左儿子是从根部来的，右儿子是到 deep 更深的地方，如果点 y 的左儿子没有的话，我们也需要直接返回，直接进行 cut 操作会破坏原树的性质

Splay-Tree的操作

在LCT中，Splay 的操作和一般的 Splay 操作略不同（我在这里卡了死循环…）我们来看看有哪些不同的操作

  • isroot

我们在 Splay 中判断根的方式是该根是否有父亲节点，但是在LCT中有很多棵 Splay ，在这棵 Splay 中的根可能指向别的树的节点，这样我们就找不到根了…
所以我们需要反过来，判断该点的父亲节点的儿子是否有该点，即求该点的父亲节点的偏好子节点是否为该点，我们来看一下代码实现

1
2
3
inline bool isroot(int x){
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
  • rotate

我们在进行旋转操作的时候还是要多加入一句话
如果旋转的点 i 的爷爷节点与 i 并不是在同一棵树上的话，我们就不需要把 i 的爷爷节点的儿子指向 i （否则破坏性质
来看一下整个的代码实现（其实80%差不多

1
2
3
4
5
6
inline void rotate(int x){
    int y=fa[x],z=fa[y],d=(ch[y][1]==x);
    if (!check(y)) ch[z][ch[z][1]==y]=x;
    ch[y][d]=ch[x][!d],fa[ch[x][!d]]=y;
    ch[x][!d]=y,fa[y]=x;fa[x]=z;update(y);	
}
  • Splay

Splay 操作也是有很多不同的（因此我拉了模板的 Splay 之后才发现死循环的原因…
我们在进行伸展的时候，是不能伸展到别的树的，然后我们需要释放标记（我们上面讲过的翻转标记
用一个小堆栈维护，我们一直向上找父亲节点，然后把这一条路径上的标记释放，看一下代码实现

1
2
3
4
5
6
7
8
inline void splay(int x){
    stack[top=1]=x; for (int i=x;!check(i);i=fa[i]) stack[++top]=fa[i];
    for (int i=top;i>=1;i--) push_down(stack[i]);
    for (int y=fa[x],z=fa[y];!check(x);y=fa[x],z=fa[y]){
        if (!check(y)){((ch[z][0]==y)^(ch[y][0]==x))?rotate(x):rotate(y);}
        rotate(x);
    } update(x);
}

再看一下标记的释放

1
2
3
4
5
6
inline void push_down(int x){
    if(tag[x]) {
        tag[ch[x][0]]^=1,tag[ch[x][1]]^=1;
        swap(ch[x][0],ch[x][1]);tag[x]=0;
    }
}
其他操作简述

实际上我们还可以用 LCT 求LCA，我在这里就不多解释了（我也不会…

关于询问实际上就是求 Splay 维护的信息，也是很简单的

这样我觉得我讲的还是蛮详细的，这是入门的LCT，我们现在来看一下模板题

题目

题目描述

给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

输入输出格式

输入格式：

第1行两个整数，分别为n和m，代表点数和操作数。

第2行到第n+1行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。

第n+2行到第n+m+1行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式：

对于每一个0号操作，你须输出x到y的路径上点权的xor和。

输入输出样例

输入样例#1：
3 3 
1
2
3
1 1 2
0 1 2 
0 1 1
输出样例#1：
3
1

说明

数据范围：1 ≤ N , M ≤ 3*105

解题过程

  • 赤裸裸的模板…
  • 它叫你干嘛你就干嘛…
  • 所有操作在上面都有讲过…
  • 但是好像LCT跑的不是很快…（起码我觉得
  • 话说LCT的代码可以压成19行也是蛮好看的…
  • LCT这种数据结构一定要多练也很容易写错的…

AC代码氧气656ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define drep(i,a,b) for(re i=(a);i>=(b);--(i))

using namespace std;

const int N=300010;
int n,m;
struct LCT{
    int a[N],fa[N],ch[N][2],tag[N],sum[N],stack[N],top;
    inline bool check(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    inline void push_down(int x){
        if(tag[x]) {
            tag[ch[x][0]]^=1,tag[ch[x][1]]^=1;
            swap(ch[x][0],ch[x][1]);tag[x]=0;
        }
    }
    inline void update(int x){sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^a[x];}
    inline void rotate(int x){
        int y=fa[x],z=fa[y],d=(ch[y][1]==x);
        if (!check(y)) ch[z][ch[z][1]==y]=x;
        ch[y][d]=ch[x][!d],fa[ch[x][!d]]=y;
        ch[x][!d]=y,fa[y]=x;fa[x]=z;update(y);	
    }
    inline void splay(int x){
        stack[top=1]=x; for (int i=x;!check(i);i=fa[i]) stack[++top]=fa[i];
        for (int i=top;i>=1;i--) push_down(stack[i]);
        for (int y=fa[x],z=fa[y];!check(x);y=fa[x],z=fa[y]){
            if (!check(y)){((ch[z][0]==y)^(ch[y][0]==x))?rotate(x):rotate(y);}
            rotate(x);
        }update(x);
    }
    inline int access(int x){
        int t=0;
        while(x){splay(x);ch[x][1]=t;t=x;x=fa[x];}
        return t;
    }
    inline int find(int x){
        access(x);splay(x);int now=x;
        while(ch[now][0]!=0) now=ch[now][0];return now;
    }
    inline void makeroot(int x){access(x);splay(x);tag[x]^=1;}
	inline void link(int x,int y){makeroot(x); if(find(x)!=find(y)) fa[x]=y;}
	inline void cut(int x,int y){
		makeroot(x);access(y);splay(y);
		if(fa[x]!=y||ch[x][1]) return;
		fa[x]=0;ch[y][0]=0;
	}
    inline void change(int x,int y){sum[x]=sum[x]^a[x]^y;a[x]=y;}
    inline int query(int x,int y){makeroot(x);access(y);splay(y);return sum[y];}
}LCT;

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&LCT.a[i]);
    while(m--){
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==0) {printf("%d\n",LCT.query(x,y));}
        else if(opt==1) {if(LCT.find(x)!=LCT.find(y)) LCT.link(x,y);}
        else if(opt==2)	{LCT.cut(x,y);}
        else if(opt==3) {LCT.change(x,y);}
    }
    return 0;
}

为了方便看我就放在结构体里写函数了，可能加个读优616ms…

后记

关于LCT其实也蛮详细的了
我本来想再拉一道LCT的例题那就改天吧
欢迎指正…我觉得我好菜啊
有时候一天一篇博客也是挺累的…
而且昨天博客出锅修了我好久…
本人联系方式如下（因为懒得挂评论啊…

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan