「Learning Notes」Link-Cut Tree

Basic Concepts

Preferred Child

如果在 x 的子树中最后被 access 的点处于以节点 x 的子节点 y 为根的子树中,那么称节点 y 为节点 x 的 Preferred Child.

Preferred Edge

称从节点 x x 的 Preferred Child 的边为 Preferred Edge.

Preferred Path

称由 Preferred Edge 组成的不可延伸的路径为 Preferred Path.

Auxiliary Tree

Auxiliary Tree 维护着原树中的 Preferred Path,每棵 Auxiliary Tree 都对应着原树中的一条 Preferred Path,通常使用 splay 来实现。
原树中的轻边(即非 Preferred Edge 的边)由 Auxiliary Tree 根节点的单向父指针维护。
即如果 \left<x,y\right> 是一条轻边(节点 x 为节点 y 的父亲),则只能单向地通过节点 y 所在的 Auxiliary Tree 的根节点的父指针访问其在原树中的父节点 x ,而不能从节点 x 访问到其子节点 y 所在的 Auxiliary Tree.

Notice

Auxiliary Tree 为一棵二叉排序树,其关键字为节点在原树中的深度,但该深度并不储存在节点中。
(更好的理解应该是:对每一棵 Auxiliary Tree 进行中序遍历得到的节点序列,该序列在原树中的深度应该是递增的)

Path Parent

称每条 Preferred Path 所对应的 Auxiliary Tree 的根节点的父指针指向的节点为该 Preferred Path 的 Path Parent.

Link-Cut Tree 即一个由 Auxiliary Tree 构成的森林,Auxiliary Tree 之间通过每棵 Auxiliary Tree 的根节点的父指针联系起来.

Operations

「Access」

The Central Operation of Link-Cut Tree
访问一个节点 切断其与其原先的 Preferred Child 的联系 并使得根节点到该节点的路径变为 Preferred Path.

首先由于 Preferred Path 的定义,如果一个点被访问,那么这个点到根节点的所有的边都会变成 Preferred Edge.
由于每个点只有一个 Preferred Child,所以这个点到根节点路径上的所有的点都会和原来的 Preferred Child 断开,连接到这条新的 Preferred Path 上.
假设对节点 x 执行 access 操作,那么先将节点 x 伸展到对应 Auxiliary Tree 的根节点。
因为被访问的点是没有 Preferred Child 的,所以在 Auxiliary Tree 中断开根节点 x 与其右子树的联系,保留其左子树,并将这棵树的 Path Parent 伸展到其所在 Auxiliary Tree 的根节点,断开其与其右子树的联系,连接该节点与节点 x (即合并两棵 Auxiliary Tree).
不断地重复这一操作,直到节点 x 当前所在 Auxiliary Tree 的 Path Parent 不存在时停止,表示已经完成 access 操作.

Notice: access 时记得维护节点信息!

1
2
3
4
inline void access(int o){
for(int k=0;o;k=o,o=Fa(o))
splay(o),rs(o)=k,update(o);
}

「isroot」

判断节点 x 是否为其所在 Auxiliary Tree 的根.

判断该节点是否为其所在 Auxiliary Tree 的根节点,即判断它是否为其父节点的子节点(见 Auxiliary Tree).

1
2
inline bool isroot(const int&o)
{return ls(Fa(o))!=o&&rs(Fa(o))!=o;}

「MakeRoot」

使节点 x 成为原树的根.

只需要对节点 x 执行 access 操作,使得节点 x 与根节点处于同一棵 Auxiliary Tree 上,再将节点 x 伸展到根,对节点 x 所在的整棵 Auxiliary Tree 进行翻转即可。
因为Auxiliary Tree节点的关键字是其在原树中的深度(见 Auxiliary Tree),所以在 access x 后,设对节点 x 所在 Auxiliary Tree 进行中序遍历得到的序列为 T ,则 T 应以原根为首,以节点 x 结尾, T 中节点在原树上的深度递增.
那么在将 x makeroot 后,序列 T 中的节点在原树上的深度递减(原 Preferred Path 是 root-> x ,而新 Preferred Path 则是 x ->root).
所以为了维护 Auxiliary Tree 的性质,对新根节点 x 所在的 Auxiliary Tree 进行翻转,使得节点 x 所在 Auxiliary Tree 进行中序遍历得到的节点序列在原树上的深度重新由递减变为递增.

1
2
inline void MakeRoot(const int&o)
{access(o);splay(o);rev(o)^=1;}

「FindRoot」

找到节点 x 在原树上所属的树的根.

只需对节点 x 执行 access 操作,再将节点 x 伸展到根,在其左子树中找到关键字(即其在原树中的深度)最小的节点即可。

Notice:FindRoot 后应当将找到的 root splay 到其所在的 Auxiliary Tree 的根!

1
2
3
4
5
inline int FindRoot(int o){
access(o);splay(o);
for(;ls(o);o=ls(o));
return splay(o),o;
}

「Link」

在原树上连接节点 x 和节点 y (使节点 x 成为节点 y 的子节点).

只需将节点 x makeroot,再将节点 x 的父指针指向节点 y 即可。

1
2
inline void lnk(const int&x,const int&y)
{MakeRoot(x);Fa(x)=y;}

「Cut」

在原树上断开连接节点 x 与节点 y 的边.

只需将节点 x makeroot,再对节点 y 执行 access 操作并将其伸展到其所在 Auxiliary Tree 的根,使节点 x 和节点 y 处于同一棵 Auxiliary Tree 上.
此时若节点 x 为节点 y 的左子节点,则说明在原树上存在边 \left<x,y\right> ,此时断开节点 x 与节点 y 的联系即可。

1
2
3
4
inline void cut(const int&x,const int&y){
MakeRoot(x);access(y);splay(y);
if(ls(y)==x)ls(y)=Fa(x)=0;
}

Code

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
struct Node{
int lson,rson,p,sth/*Some Infomation you need*/;
bool rev;
Node():lson(0),rson(0),p(0),sth(0),rev(false){}
}node[maxn+1];
#define ls(o) node[o].lson
#define rs(o) node[o].rson
#define Fa(o) node[o].p
#define Sth(o) node[o].sth
#define rev(o) node[o].rev

inline void update(const int&o)
{/*Maintain the Infomation you need*/}

inline void push_down(const int&o){
if(rev(o)){
swap(ls(o),rs(o));
rev(ls(o))^=true;rev(rs(o))^=true;
rev(o)=false;
}
}

inline bool isroot(const int&o)
{return ls(Fa(o))!=o&&rs(Fa(o))!=o;}

inline void rotate(const int&o){
int p=Fa(o),gp=Fa(p);
if(!isroot(p))ls(gp)==p?ls(gp)=o:rs(gp)=o;
Fa(Fa(p)=o)=gp;
if(ls(p)==o)ls(Fa(rs(o))=p)=rs(o),rs(o)=p;
else rs(Fa(ls(o))=p)=ls(o),ls(o)=p;
update(p);update(o);
}

inline void splay(const int&o){
static int stk[maxn+1],*stp=stk;
*++stp=o;
for(int i=o;!isroot(i);i=Fa(i))
*++stp=Fa(i);
for(;stp!=stk;)
push_down(*stp--);

for(;!isroot(o);rotate(o))
if(!isroot(Fa(o)))
rotate(((ls(Fa(o))==o)^(ls(Fa(Fa(o)))==Fa(o)))?o:Fa(o));
}

inline void access(int o){
for(int k=0;o;k=o,o=Fa(o))
splay(o),rs(o)=k,update(o);
}

inline void MakeRoot(const int&o){access(o);splay(o);rev(o)^=1;}

inline int FindRoot(int o){
access(o);splay(o);
while(ls(o))o=ls(o);
return(splay(o),o);
}

inline void lnk(const int&x,const int&y)
{MakeRoot(x);Fa(x)=y;}

inline void cut(const int&x,const int&y){
MakeRoot(x);access(y);splay(y);
if(ls(y)==x)ls(y)=Fa(x)=0;
}

Usage

Link-Cut Tree一般用来处理要求支持断边连边,修改点权与简单路径查询的问题。
修改与查询路径 \left<x,y\right> 时一般先将节点 x makeroot,再对节点 y 执行 access 操作,此时链 \left<x,y\right> 全部处在节点 x 所在的 Auxiliary Tree 中,对该 Auxiliary Tree 进行修改|查询即可。