浅谈Link Cut Tree

(Updated: )
oi

前言

Link Cut Tree 可真是好用呢~

刚入门的各位不需要担心，LCT其实十分简单。

陈指导写的LCT也不过10几行，我这个菜鸡打的模板也只有50+行。

所以LCT码量很小

好了，步入正题。

正文

简介

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

  • Add a tree consisting of a single node to the forest.
  • Given a node in one of the trees, disconnect it (and its subtree) from the tree of which it is part.
  • Attach a node to another node as its child.
  • Given a node, find the root of the tree to which it belongs. By doing this operation on two distinct nodes, one can check whether they belong to the same tree.

The represented forest may consist of very deep trees, so if we represent the forest as a plain collection of parent pointer trees, it might take us a long time to find the root of a given node. However, if we represent each tree in the forest as a link/cut tree, we can find which tree an element belongs to in O(log(n)) amortized time. Moreover, we can quickly adjust the collection of link/cut trees to changes in the represented forest. In particular, we can adjust it to merge (link) and split (cut) in O(log(n)) amortized time.

Link/cut trees divide each tree in the represented forest into vertex-disjoint paths, where each path is represented by an auxiliary data structure (often splay trees, though the original paper predates splay trees and thus uses biased binary search trees). The nodes in the auxiliary data structure are ordered by their depth in the corresponding represented tree. In one variation, Naive Partitioning, the paths are determined by the most recently accessed paths and nodes, similar to Tango Trees. In Partitioning by Size paths are determined by the heaviest child (child with the most children) of the given node. This gives a more complicated structure, but reduces the cost of the operations from amortized O(log n) to worst case O(log n). It has uses in solving a variety of network flow problems and to jive data sets.

In the original publication, Sleator and Tarjan referred to link/cut trees as “dynamic trees”, or “dynamic dyno trees”.

——Wikepedia

当然你看不懂也没关系

简单的来说动态树(Link Cut Tree)是一个可以维护动态森林的树形结构，它有类似于树链剖分(重链剖分)、长链剖分的轻、重链的虚、实边，但不同的是，动态树的虚、实边是可以变换的(虚边变实边，实边变虚边)，并且用Splay来维护每一条实路径。

Link Cut Tree的基本操作复杂度均摊$O({\log}N)$，但常数较大，一般效率会低于树链剖分，但是却能解决许多树链剖分解决不了的问题。

所以，如果你还不会Splay，请左转这篇Blog。

性质

Link Cut Tree有许多性质，差不多就这些了：

  • 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。(就是链)
  • 每个节点包含且仅包含于一个Splay中，每一个父亲的向儿子的连边中有且只有一条边是实边
  • 所有的实边包含在Splay中，而虚边总是指向另一个Splay中的某个节点(指向该Splay中中序遍历最靠前的点在原树中的父亲)
  • 所有的实边的父亲和儿子都要标记，虚边只要儿子记父亲(实边认父又认子，虚边认父不认子)

听不懂？没关系，看图就会了。

红色圆圈代表一个Splay

一开始，所有的边都是虚边，每个点都是一个Splay。

绿色代表实边，其相连的代表一个Splay

后来，我们选了一些边为实边。这样也是符合的。

相信你看了图以后就知道LCT大概长什么样了。

操作

定义

文字、代码中将要用到的变量名&定义。

变量名

定义

fa[x]

节点x的父亲(father)

v[x]

节点x的权值(value)

s[x]

节点x及其子树的权值和(sum)

tag[x]

节点x的翻转情况

ch[x][0/1]

节点x的左/右儿子(children)

简介

这里先给出将要介绍的基本操作的用途，看不懂没关系，接下来会图解+代码说明。

操作名称

用途

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)

这是Link Cut Tree中最基础、最重要的操作。

就是将x到原树根节点之间的链丢到一个Splay中。

听不懂？没关系，来图解。

比如还是这棵树，我们要执行access(9)。

显然，它会变成这样。

1-2-5-9变成实边

路径上所有点的其他儿子连的边变成虚边

整理一下：

  1. 转到根
  2. 换儿子
  3. 更新信息
  4. 当前操作点切换为轻边所指的父亲，转1。

详细图解一下：

而下一次操作需要Splay(2)，此时树的形态会发生巨大转变。

然后我们就完成了

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

因为fa[x]的深度小于x，而在Splay里fa[x]是x的父亲，所以x在Splay里是fa[x]的右儿子。

上代码：

1
2
3
4
5
6
7
inline void access(int x){
for(int y=0;x;x=tr[y=x].fa){//当前操作点转到轻边所指的父亲 
splay(x),//转到根 
tr[x].ch[1]=y,//换儿子 
pushup(x);//更新信息 
} 
}

findroot(x)

因为根节点的深度是最小的，所以我们可以从x向上找，使用access将x和x的根节点弄到同一个Splay中。

因为在执行access操作后，这棵Splay里的节点权值最大的就是x。

由于二叉搜索树(Binary Search Tree)的性质：x的左子树<x<x的右子树

所以我们可以把x转成根节点，那么最左边的那个节点便是这棵树的根节点了。

代码实现：

1
2
3
4
5
6
7
8
9
inline int findroot(int x){
access(x);//Access将x和根节点弄到同一个Splay中
splay(x);//把x转到Splay的根节点 
while(tr[x].ch[0]){
pushdown(x),//更新节点信息(可能有翻转标记，之后会提到) 
x=tr[x].ch[0];//不断找左儿子 
}
return x;
}

makeroot(x)

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

我们可以先access(x)，把x到根节点打通成一条链。

我们发现x一定是在它所在的辅助树的中序遍历的最后一个的(因为它是这条链上最深的点)。

我们把x点Splay到Splay的根，那么x显然是没有右子树的。

我们要实现把x移到原树的根，也就是把x到根这条链的深度全部翻转一遍。

在Splay上体现就是把整棵树反转一次。

我们可以写个翻转标记来减小复杂度。

1
2
3
4
5
6
7
8
9
inline void flip(int x){//翻转操作 
swap(tr[x].ch[0],tr[x].ch[1]);//交换 
tr[x].tag^=1;//标记 
}
inline void makeroot(int x){
access(x);//把x到根节点打通 
splay(x);//把x变成根 
flip(x);//翻转 
}

split(x,y)

把x和y放在同一个Splay中，并以y为根

首先我们并不能保证x和y一定在同一条链里，所以我们要先把x变成原树的根节点，然后access(y)，这样就会把x到y之间所有节点弄到同一个Splay里了。

最后**Splay(y)**，以y为根。

1
2
3
4
5
inline void split(int x,int y){
makeroot(x);//把x变成原树的根节点 
access(y);//把x到y之间所有节点弄到同一个Splay里 
splay(y);//以y为根 
}

把x和y的原树连接起来

首先把x换成原树的根，然后再判断y的根是否是x。因为x和y连接起来一定是x和y在不同树中，所以若y的根是x则不需要连接。

1
2
3
4
inline void link(int x,int y){
makeroot(x);//把x换成原树的根 
if(findroot(y)!=x) tr[x].fa=y;//判断y的根是否是x，连虚边 
}

cut(x,y)

把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 的整数了)

但是，很遗憾，因为我们要使用findroot(y)，所以中途会splay(x)。

所以其他条件全部反过来。

1
2
3
4
inline void cut(int x,int y){
split(x,y);
if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ch[1]) tr[x].fa=tr[y].ch[0]=0,pushup(y);//findroot中有Splay，cut中x和y的父子关系会发生改变 
}

Rotate改动

需要特判一下连虚边的情况

如果z(x的爷爷)不存在，则只需要连虚边

1
2
3
4
5
6
7
8
inline void rotate(int x){
int y=tr[x].fa,z=tr[y].fa,k=tr[y].ch[1]==x,v=tr[x].ch[!k];
if(!isroot(y)) tr[z].ch[tr[z].ch[1]==y]=x;//特判虚边
tr[x].ch[!k]=y,tr[y].ch[k]=v;//普通Rotate
if(v) tr[v].fa=y;
tr[y].fa=x;tr[x].fa=z;
pushup(y);pushup(x);
}

Splay改动

要注意下Splay只能到Splay的根节点，所以需要先记录下这条链的所有节点，用栈即可

1
2
3
4
5
6
7
8
9
10
11
inline void splay(int x){
int y=x,z;top=0;stk[++top]=y;
while(!isroot(y)) stk[++top]=y=tr[y].fa;//开个栈记录下
while(top) pushdown(stk[top--]);//下传
while(!isroot(x)){//普通Splay
y=tr[x].fa;z=tr[y].fa;
if(!isroot(y)) rotate((tr[y].ch[0]==x)^(tr[z].ch[0]==y)?x:y);
rotate(x);
}
pushup(x);
}

模板题

题目链接：P3690 【模板】Link Cut Tree （动态树）

模板题不需要讲了吧，直接上代码：

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
#include<bits/stdc++.h>
using namespace std;
inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();return res*f;}
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
struct node{int fa,v,s,ch[2],tag;}tr[100010];
int stk[100010],top;
inline bool isroot(int x){return tr[tr[x].fa].ch[0]!=x&&tr[tr[x].fa].ch[1]!=x;}
inline void pushup(int x){tr[x].s=tr[tr[x].ch[0]].s^tr[tr[x].ch[1]].s^tr[x].v;}
inline void flip(int x){swap(tr[x].ch[0],tr[x].ch[1]);tr[x].tag^=1;}
inline void pushdown(int x){
if(!tr[x].tag) return ;
if(tr[x].ch[0]) flip(tr[x].ch[0]);
if(tr[x].ch[1]) flip(tr[x].ch[1]);
tr[x].tag=0;
}
inline void rotate(int x){
int y=tr[x].fa,z=tr[y].fa,k=tr[y].ch[1]==x,v=tr[x].ch[!k];
if(!isroot(y)) tr[z].ch[tr[z].ch[1]==y]=x;
tr[x].ch[!k]=y,tr[y].ch[k]=v;
if(v) tr[v].fa=y;
tr[y].fa=x;tr[x].fa=z;
pushup(y);pushup(x);
}
inline void splay(int x){
int y=x,z;top=0;stk[++top]=y;
while(!isroot(y)) stk[++top]=y=tr[y].fa;
while(top) pushdown(stk[top--]);
while(!isroot(x)){
y=tr[x].fa;z=tr[y].fa;
if(!isroot(y)) rotate((tr[y].ch[0]==x)^(tr[z].ch[0]==y)?x:y);
rotate(x);
}
pushup(x);
}
inline void access(int x){for(int y=0;x;x=tr[y=x].fa) splay(x),tr[x].ch[1]=y,pushup(x);}
inline void makeroot(int x){access(x);splay(x);flip(x);}
inline int findroot(int x){access(x);splay(x);while(tr[x].ch[0]) pushdown(x),x=tr[x].ch[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) tr[x].fa=y;}
inline void cut(int x,int y){split(x,y);if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ch[1]) tr[x].fa=tr[y].ch[0]=0,pushup(y);}
int n,m,x,y,op;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) tr[i].v=read();
for(int i=1;i<=m;i++){
op=read(),x=read(),y=read();
if(op==0) split(x,y),write(tr[y].s),putchar('\n');
else if(op==1) link(x,y);
else if(op==2) cut(x,y);
else splay(x),tr[x].v=y;
}
}

写在最后

大家可以再找一点例题，这里放个链接。

终于写完了，完结撒花*★,°*:.☆(￣▽￣)/$:*.°★* 。