Link-Cut Tree

Link-Cut Tree

Link-Cut Tree(动态树)

本文章中的部分代码和思路来自于 Link Cut Tree - OI Wiki

定义

LCT 用来解决动态树的问题,即一张图任意时刻一定是一个森林,每次可以删除一条边或者加入一条边,并且还要在线维护两个点之间路径的信息,于是 LCT 便应运而生了。

辅助树

首先 LCT 有自己的一套轻重链剖分关系,它并不像树链剖分那样是选择重儿子延伸重链,而是选择他最近访问过的儿子延伸重链,像全局平衡二叉树那样,每条重链会额外维护一个 Splay(如果是 Treap 时间复杂度不优秀),然后存储若干信息,其中 Splay 根节点的父亲就是这条重链链头的父亲,这条边是虚边,其他边都是实边。

最开始 LCT 每个点自己属于自己一个 Splay,即所有边都是轻边。

操作

判断根节点-Isroot

这个函数特别简单,它的意思是判断 x 是不是它所在 Splay 的根节点,因为 Splay 的根节点的父亲是这个 Splay 所代表重链的链头的父亲,根据上述表述,可以写出:

1
2
3
// 在前面我们已经说过,LCT 具有 如果一个儿子不是实儿子,他的父亲找不到它的性质
// 所以当一个点既不是它父亲的左儿子,又不是它父亲的右儿子,它就是当前 Splay 的根
#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

下放标记-Update

从上到下下放 p 的所有祖先的标记,很简单:

1
2
3
4
5
// 从上到下一层一层 pushDown 即可
void Update(int p) {
if (!isRoot(p)) Update(f[p]);
pushDown(p);
}

旋转-Splay

这里的 rotate 函数和 splay 函数都有些许不同,splay 函数中要先把 x 的所有祖先的标记都下放了之后才能开始旋转,然后 rotate 函数中当 y 不是根节点的时候才能改变 x,z 两者之间的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define Get(x) (ch[f[x]][1] == x)

void Rotate(int x) {
int y = f[x], z = f[y], k = Get(x);
if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
// 上面这句一定要写在前面,普通的 Splay 是不用的,因为 isRoot
ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
ch[x][!k] = y, f[y] = x, f[x] = z;
PushUp(y), PushUp(x);
}

void Splay(int x) {
Update(x);
for (int fa; fa = f[x], !isRoot(x); Rotate(x)) {
if (!isRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
}
}

访问-Access

这个操作是最重要的操作,它可以让一个节点 x 的重链链头成为根节点,相当于把 x 到根节点上的所有边变成重边,原来处在 x 到根路径上的点的重边都删去。

函数可以写成下面的形式,如果有 tag 一定要在 Splay 函数中下放。

1
2
3
4
5
6
7
8
9
10
// Access 是 LCT
// 的核心操作,试想我们像求解一条路径,而这条路径恰好就是我们当前的一棵 Splay,
// 直接调用其信息即可。先来看一下代码,再结合图来看看过程
int Access(int x) {
int p;
for (p = 0; x; p = x, x = f[x]) {
Splay(x), ch[x][1] = p, PushUp(x);
}
return p;
}

换根-Makeroot

首先 access(x),然后把 x 所在平衡树做一个文艺平衡树中的区间翻转即可。

1
2
3
4
5
void makeRoot(int p) {
p = Access(p);
swap(ch[p][0], ch[p][1]);
tag[p] ^= 1; //区间翻转的 tag
}

Link 操作只需要把 x 旋转到根节点(树的根节点以及其 Splay 的根节点),然后直接连接到 y 上即可。

1
2
3
4
5
void Link(int x, int y) {
makeRoot(x);
splay(x);
f[x] = y;
}

分裂-Split

这个函数的意义在于拿出一棵 Splay 只维护 x,y 这条链的信息,于是这样就可以了:

1
2
3
4
5
void Split(int x, int y) {
makeRoot(x);
access(y);
splay(y);
}

断边-Cut

首先判断合不合法,然后利用 split 函数把 xy 这条链拿出来,断开即可,注意 pushup 和清空的细节问题:

1
void Cut(int x, int p) { makeRoot(x), Access(p), Splay(p), tr[p].ch[0] = f[x] = 0; }

查询-Find

这个函数是查询 x原树上的根,首先 access 一下,然后暴力 splay,最后暴力跳左儿子即可,根据 splay 的性质,最后要 splay 一下根节点复杂度才有保证。(记得 pushdown

1
2
3
4
5
6
7
8
int Find(int p) {
Access(p);
Splay(p);
pushDown(p);
while (ls) p = ls, pushDown(p);
Splay(p);
return p;
}

维护链信息

通过 split 和普通的 splay 树的左右子树合并即可维护和查询,此处不做过多展开。

维护连通

通过 find 即可维护动态加边删边的连通性问题。

维护边权

对每条边新建一个点即可,在 pushuppushdown 的时候不考虑节点上的权值就好。

维护边双连通

只支持加边。

考虑加边的时候相当于把这条边所在的链缩成了一个点,用 LCT 跳跃,并查集合并即可。

维护子树信息

LCT 不能够较好地维护子树信息,但是只要有办法记录虚边连接的子树信息(例如子树节点数量等)就可以在 O(nlogn) 的时间复杂度内维护。

(这个信息要支持撤销,即有可减性,否则无法维护)

(同时维护子树信息改的地方有点多,一定要注意细节)

时间复杂度

经过势能分析,时间复杂度为大常 O(nlogn),如果把 splay 换成 Treap 的话,时间复杂度就是普通的 O(nlog2n)

下面以 P3690 【模板】动态树(LCT) 为例,给出 LCT 的示例代码:

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
#include<bits/stdc++.h>
#define get(x) (tr[tr[x].fa].ch[1]==x)
#define ll long long
#define N 100005
using namespace std;
struct node{ll ch[2],val,tag,fa,siz,p;}tr[N];
inline void pushup(ll p){
tr[p].p = (tr[tr[p].ch[0]].p ^ tr[tr[p].ch[1]].p ^ tr[p].val);
tr[p].siz = tr[tr[p].ch[0]].siz + 1 + tr[tr[p].ch[1]].siz;
}
inline void pushtag(ll p){
if(!p) return ;
swap(tr[p].ch[0],tr[p].ch[1]),tr[p].tag^=1;
}
inline void pushdown(ll p){if(tr[p].tag) pushtag(tr[p].ch[0]),pushtag(tr[p].ch[1]),tr[p].tag=0;}
inline bool isroot(ll p){return tr[tr[p].fa].ch[0]!=p&&tr[tr[p].fa].ch[1]!=p;}
inline void upd(ll p){pushup(p);if(!isroot(p)) upd(tr[p].fa);pushdown(p);}
inline void rotate(ll p){
ll y=tr[p].fa,z=tr[y].fa,k=get(p);
if(!isroot(y)) tr[z].ch[tr[z].ch[1]==y]=p;
tr[y].ch[k]=tr[p].ch[!k],tr[tr[p].ch[!k]].fa=y,tr[p].ch[!k]=y,tr[y].fa=p,tr[p].fa=z;
pushup(y),pushup(p);
}
inline void splay(ll p){
upd(p);
for(ll f;f=tr[p].fa,!isroot(p);rotate(p)) if(!isroot(f)) rotate(get(f)==get(p)?f:p);
}
inline ll access(ll p){ll i;for(i=0;p;i=p,p=tr[p].fa) splay(p),tr[p].ch[1]=i,pushup(p);return i;}
inline void makeroot(ll p){pushdown(p),access(p),splay(p),pushtag(p),pushup(p);}
inline void link(ll x,ll y){pushdown(x),pushdown(y),makeroot(x),splay(x),tr[x].fa=y,pushup(x),pushup(y);}
inline void cut(ll x,ll y){pushdown(x),pushdown(y),makeroot(x),access(y),splay(y),tr[x].fa=0,tr[y].ch[0]=0,pushup(x),pushup(y);}
inline ll find(ll p){
access(p),splay(p),pushdown(p);
while(tr[p].ch[0]) p=tr[p].ch[0],pushdown(p);
splay(p);
return p;
}
inline ll query(ll x,ll y){return makeroot(x),access(y),splay(y),tr[y].p;}
ll n,m,i,opt,x,y,z;
map<ll,ll> maps[N];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(i=1;i<=n;i++) cin>>tr[i].val,tr[i].siz=1,tr[i].p=tr[i].val;
while(m--){
cin>>opt;
if(opt==0){
cin>>x>>y;
cout<<query(x,y)<<endl;
}
if(opt==1){
cin>>x>>y;
if(find(x)==find(y)) continue;
link(x,y),maps[x][y]++,maps[y][x]++;
}
if(opt==2){
cin>>x>>y;
if(maps[x][y]) maps[x][y]--,maps[y][x]--,cut(x,y);
}
if(opt==3){
cin>>x>>y;
tr[x].val = y,access(x);
}
}
return 0;
}

注意:一定要在合适的时候 pushdownpushup,不然很容易出错。