Link-Cut Tree

Link-Cut Tree

七月 14, 2024

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 函数把 $x \to y$ 这条链拿出来，断开即可，注意 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 即可维护动态加边删边的连通性问题。

维护边权

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

维护边双连通

只支持加边。

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

维护子树信息

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

（这个信息要支持撤销，即有可减性，否则无法维护）

（同时维护子树信息改的地方有点多，一定要注意细节）

时间复杂度

经过势能分析，时间复杂度为大常 $O(n \log n)$，如果把 splay 换成 Treap 的话，时间复杂度就是普通的 $O(n \log^2 n)$。

下面以 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;
}

注意：一定要在合适的时候 pushdown 和 pushup，不然很容易出错。