连接切割树

学习笔记
5.1k 词

Link Cut Tree 可以用来维护动态树（树的形态会变化，支持加边删边）的信息。

实链剖分

对于树上每个节点连向儿子的所有边，任意选择至多一条进行剖分。我们称选择的边为实边，连接的儿子为实儿子，其余边为虚边，连接的儿子为虚儿子。

实际上就是任意剖分，因为是任意的所以可以由我们随意改变以满足动态树的要求。

辅助树

对于每一条实链都建一棵 Splay，其中序遍历是该链上点按深度从小到大排序。然后对于每棵 Splay，其根向该实链顶的父亲连一条虚边，这条虚边与 Splay 上的边的区别在于虚边认父不认子，即无法从父亲通过虚边访问儿子。

容易发现可以通过辅助树还原出原树，因此我们只需要维护辅助树而不需要维护原树。

例子：

原树为：

辅助树为：

（图源 OI Wiki）

节点信息

对于辅助树上每个节点，因为是 Splay，所以需要维护父亲 fafa，左右儿子 son0/1son _ {0 / 1}，子树大小 sizsiz。下面会讲到需要支持 reverse 操作，因此需要维护翻转标记 swpswp，以及题目要求的信息。

以上信息在代码中分别记为 fa，son[0]，son[1]，siz，swp。

基础操作

pushup / pushdown

更新节点信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
void pushup(int now) {
	siz[now] = siz[son[now][0]] + siz[son[now][1]] + 1;
	// Update other Information.
	return ;
}
void pushdown(int now) {
	if(!swp[now]) return ;
	swap(son[now][0], son[now][1]);
	swp[son[now][0]] ^= 1, swp[son[now][1]] ^= 1;
	swp[now] = 0;
	// Update other Information.
	return ;
}

isRoot

判断当前节点是否是其所在 Splay 的根。

1
int isRoot(int now) {return now != son[fa[now]][0] && now != son[fa[now]][1];}

get / rotate / splay

Splay 的基本操作，get(x)get(x) 获取 xx 是左儿子还是右儿子，rotate(x)rotate(x) 将点 xx 往上旋转，splay(x)splay(x) 将点 xx 转到当前 Splay 的根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int get(int now) {return now == son[fa[now]][1];}
void rotate(int x) {
	int y = fa[x], z = fa[fa[x]], chk = get(x);
	if (!isRoot(y)) son[z][get(y)] = x;
	son[y][chk] = son[x][chk ^ 1], fa[son[x][chk ^ 1]] = y;
	son[x][chk ^ 1] = y, fa[y] = x;
	fa[x] = z;
	pushup(y), pushup(x);
	return ;
}
void splay(int now) {
	vector<int> stk;
	stk.push_back(now);
	for (int i = now; !isRoot(i); i = fa[i]) stk.push_back(fa[i]);
	while (!stk.empty()) pushdown(stk.back()), stk.pop_back();
	// 在旋转之前将路径上所有点的标记都下传
	for (int f; f = fa[now], !isRoot(now); rotate(now))
		if (!isRoot(f)) rotate(get(f) == get(now) ? f : now);
	return ;
}

access

accessaccess 函数是 LCT 的核心，作用是将一个点 xx 与根“打通”，即将其与根放到同一条实链中，并且 xx 是这条实链的末尾。

首先 splay(x)splay(x)，然后该 Splay 中 xx 的右子树即为这条实链 xx 以下的部分，直接将其断掉。

然后不断往上跳实链，将上面一条实链从与当前实链顶端连接处断开（方法与上面相同），然后再将这两棵 Splay 合并即可。

1
2
3
4
void access(int now) {
	for (int lst = 0; now; lst = now, now = fa[now]) splay(now), son[now][1] = lst, pushup(now);
	return ;
}

makeRoot

makeRoot(x)makeRoot(x) 的功能是时 xx 成为这棵树的根。
先 access(x)access(x) 再 splay(x)splay(x)，这样 xx 就变成了这棵 Splay 的根，并且没有右儿子。然后将整棵 Splay reverse 即可。

1
void makeRoot(int now) {access(now); splay(now); swp[now] ^= 1; return ;}

维护信息

link(u,v)link(u, v) 的功能是连接 (u,v)(u, v)。
makeRoot(u)makeRoot(u)，然后将 faufa _ u 设为 vv 即可。

1
void link(int u, int v) {makeRoot(u); fa[u] = v; return ;}

cut(u,v)cut(u, v) 则是切断 (u,v)(u, v) 这条边。
makeRoot(u)makeRoot(u)，然后 access(v)access(v)，此时得到一棵仅有 u,vu, v 的 Splay，splay(v)splay(v) 后切断 u,vu, v 之间的边即可。

1
void cut(int u, int v) {makeRoot(u); access(v); splay(v); son[v][0] = fa[u] = 0; return ;}

find

find(x)find(x) 的功能是找到 xx 所在树的根。
access(x)access(x)，然后根就是所在 Splay 最左侧的点。

注意为了保证复杂度，找到根后需要对其进行 splaysplay 操作。

1
2
3
4
5
6
7
int find(int now) {
	access(now), splay(now);
	pushdown(now);
	while (son[now][0]) now = son[now][0], pushdown(now);
	splay(now);
	return now;
}

split

为了维护一条链的信息，我们需要将其打通，并且需要他是实链。split(u,v)split(u, v) 可以将 uu 变成根并得到一棵仅包含 u,vu, v 这条链的 Splay 以满足我们的要求。

1
void split(int u, int v) {makeRoot(u); access(v); splay(u); return ;}

链修改 / 查询

对于一条端点为 u,vu, v 的链的修改 / 查询，只要 split(u,v)split(u, v) 即可。

判断两个点是否在同一棵树上

相当于判断两个点所在的树是否有同一个根。

完整代码

题目：洛谷 P3690 【模板】动态树（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
struct LinkCutTree {
	int fa[100005], son[100005][2], siz[100005], swp[100005];
	int val[100005], Xor[100005];

	void pushup(int now) {
		siz[now] = siz[son[now][0]] + siz[son[now][1]] + 1;
		Xor[now] = Xor[son[now][0]] ^ val[now] ^ Xor[son[now][1]];
		return ;
	}
	void pushdown(int now) {
		if(!swp[now]) return ;
		swap(son[now][0], son[now][1]);
		swp[son[now][0]] ^= 1, swp[son[now][1]] ^= 1;
		swp[now] = 0;
		return ;
	}
	int isRoot(int now) {return now != son[fa[now]][0] && now != son[fa[now]][1];}
	int get(int now) {return now == son[fa[now]][1];}
	void rotate(int x) {
		int y = fa[x], z = fa[fa[x]], chk = get(x);
		if (!isRoot(y)) son[z][get(y)] = x;
		son[y][chk] = son[x][chk ^ 1], fa[son[x][chk ^ 1]] = y;
		son[x][chk ^ 1] = y, fa[y] = x;
		fa[x] = z;
		pushup(y), pushup(x);
		return ;
	}
	void splay(int now) {
		vector<int> stk;
		stk.push_back(now);
		for (int i = now; !isRoot(i); i = fa[i]) stk.push_back(fa[i]);
		while (!stk.empty()) pushdown(stk.back()), stk.pop_back();
		for (int f; f = fa[now], !isRoot(now); rotate(now))
			if (!isRoot(f)) rotate(get(f) == get(now) ? f : now);
		return ;
	}
	void access(int now) {
		for (int lst = 0; now; lst = now, now = fa[now]) splay(now), son[now][1] = lst, pushup(now);
		return ;
	}
	void makeRoot(int now) {access(now); splay(now); swp[now] ^= 1; return ;}
	void link(int u, int v) {makeRoot(u); fa[u] = v; return ;}
	void cut(int u, int v) {makeRoot(u); access(v); splay(v); son[v][0] = fa[u] = 0; return ;}
	int find(int now) {
		access(now), splay(now);
		pushdown(now);
		while (son[now][0]) now = son[now][0], pushdown(now);
		splay(now);
		return now;
	}
	void split(int u, int v) {makeRoot(u); access(v); splay(u); return ;}
	void update(int u, int _val) {split(u, u); val[u] = Xor[u] = _val; return ;}
	int query(int u, int v) {split(u, v); return Xor[u];}
	int isConnected(int u, int v) {return find(u) == find(v);}
};

时间复杂度

每次操作均摊是 O(log⁡n)O(\log n) 的，证明还不会。

留言