Dyd's Blog

He who has a strong enough why can bear almost any how.

LCT

Posted on Edited on In
Symbols count in article: 3.6k Reading time ≈ 3 mins.

背模板吧

LCT

LCT，Link Cut Tree，中文叫做动态树，顾名思义，是一种维护动态的树的数据结构，可以维护一个森林，支持加边、删边操作（但必须保证是树），时间都是 $O(\log n)$ ，常数有点大

思路

其实主要思路是将一棵树拆成很多个splay

虚实边

和树剖类似，动态树将边分为虚边和实边，每一个点到其儿子节点的所有边中，最多有一条实边（可以没有），而于树剖不同的是，我们用平衡树维护实边构成的路径，具体地，每一条只由实边构成的、极大的路径（特别的，如果一个点没有实边与其相连，我们认为这个点对应一个只包含自己的实边路径）都对应一个splay，splay的中序遍历，就是要维护的路径（从上到下），而splay的后继和前驱就对应树上的父子关系，而对于虚边，我们用splay的根节点维护（具体的，根节点的父亲对于虚边上的父亲）， 如图，实线对于实边，虚线对于虚边，红色部分对于一棵splay，不难发现，在这样的定义下，所有点都对应位于的实边路径：

实虚边

为了维护虚实边，我们有以下操作

accecss

$access(x)$ 可以将树上从根节点到点 $x$ 之间的所有边变成实边（明显它们也就在同一个实边路径上了），并且 $x$ 下方再无该实边路径上的点（换句话说， $x$ 就是该实边路径的终点），这是LCT最基本的操作，执行完毕后 $x$ 就是所在splay的根，具体如图：

acess

如果要把 $x$ 和 $y$ 所在实边相连，可以把 $y$ 转到它所在splay的根，此时 $y$ 的左子树就对应 $y$ 所在实边中 $y$ 上方的部分，右子树就对应 $y$ 所在实边中 $y$ 下方的部分，然后直接让 $y$ 的右儿子指向 $x$ （我们从下往上进行，所以这时的 $x$ 是处理完毕的，并且一定是其所在实边对应slpay的根，这相当于将 $x$ 所在的splay拿来代替 $y$ 的右子树），这样， $y$ 所在实边中 $y$ 下方的部分就变成 $x$ 所在的那条实边了，特别的，第一次操作时让 $x$ 的右子树为空（保证 $x$ 就是该实边路径的终点）

要完成access，只需从 $x$ 开始向上操作，直到根节点即可

is root

$is\_rt(x)$ 可以判断 $x$ 是否是所在slpay的根节点，注意判断的不是原树的根节点，只需看 $x$ 的父亲是否有 $x$ 这个儿子即可（slpay根节点的父亲维护的时虚边）

make root

$make\_rt(x)$ 可以将 $x$ 变成所在树的根节点（因为树是无根树），只需先 $access(x)$ ，此时 $x$ 和根必定是同一实边路径的终点和起点，翻转即可

find root

$find\_rt(x)$ 可以找到 $x$ 所在树的根节点，并将其转到splay的根节点上，只需先 $access(x)$ ，然后一直向 $x$ 的左子树走即可，走时注意push down

split

$split(x, y)$ 可以将 $x$ 到 $y$ 的路径变成实边路径，只要先 $make\_rt(x)$ ，然后 $access(y)$ 即可

$link(x, y)$ 判断 $x, y$ 是否联通，如果不连通就加边 $(x, y)$ ，只要 $make\_rt(x)$ 然后判断 $find\_rt(y)$ 是否等于 $x$ 不等则令 $fa(x) = y$ （因为make root后 $x$ 一定是splay的根节点）

cut

$cut(x, y)$ 判断 $x, y$ 之间是否有边，如果有，就删除边 $(x, y)$ ，只要 $make\_rt(x)$ 然后判断 $find\_rt(y) = x \wedge fa(y) = x \wedge y\text{没有左儿子}$ ，成立就断开 $x, y$ 之间的边（双向断），然后push up

代码

【模板】动态树

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m;
struct Slpay
{
	int ch[2], fa, v;
	int sum;
	bool rev;
#define ch(x, y) tr[(x)].ch[(y)]
#define fa(x) tr[(x)].fa
#define v(x) tr[(x)].v
#define sum(x) tr[(x)].sum
#define rev(x) tr[(x)].rev
} tr[N];
int stk[N];
void tag_rev(int x)
{
	swap(ch(x, 0),ch(x, 1));
	rev(x) ^= 1;
}
void push_up(int x)
{
	sum(x) = sum(ch(x, 0)) ^ sum(ch(x, 1)) ^ v(x);
}
void push_down(int x)
{
	if (rev(x))
	{
		tag_rev(ch(x, 0)), tag_rev(ch(x, 1));
		rev(x) = 0;
	}
}
bool is_rt(int x)
{
	return ch(fa(x), 0) != x && ch(fa(x), 1) != x;
}
void rotate(int x)
{
	int y = fa(x), z = fa(y);
	int k = ch(y, 1) == x;
	if (!is_rt(y))
		ch(z, ch(z, 1) == y) = x;
	fa(x) = z;
	ch(y, k) = ch(x, k ^ 1), fa(ch(x, k ^ 1)) = y;
	ch(x, k ^ 1) = y, fa(y) = x;
	push_up(y), push_up(x);
}
void splay(int x)
{
	int top = 0, t = x;
	stk[++top] = t;
	while (!is_rt(t))
		stk[++top] = t = fa(t);
	while (top)
		push_down(stk[top--]);
	int y, z;
	while (!is_rt(x))
	{
		y = fa(x), z = fa(y);
		if (!is_rt(y))
			(ch(y, 1) == x) ^ (ch(z, 1) == y) ? rotate(x) : rotate(y);
		rotate(x);
	}
}
void access(int x)
{
	int z = x;
	for (int y = 0; x; y = x, x = fa(x))
	{
		splay(x);
		ch(x, 1) = y;
		push_up(x);
	}
	splay(z);
}
void make_rt(int x)
{
	access(x);
	tag_rev(x);
}
int find_rt(int x)
{
	access(x);
	while (ch(x, 0))
		push_down(x), x = ch(x, 0);
	splay(x);
	return x;
}
void split(int x, int y)
{
	make_rt(x);
	access(y);
}
void link(int x, int y)
{
	make_rt(x);
	if (find_rt(y) != x)
		fa(x) = y;
}
void cut(int x, int y)
{
	make_rt(x);
	if (find_rt(y) == x && fa(y) == x && !ch(y, 0))
	{
		ch(x, 1) = fa(y) = 0;
		push_up(x);
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &v(i));
	int op, x, y;
	while (m--)
	{
		scanf("%d%d%d", &op, &x, &y);
		if (op == 0)
		{
			split(x, y);
			printf("%d\n", sum(y));
		}
		else if (op == 1)
			link(x, y);
		else if (op == 2)
			cut(x, y);
		else
		{
			splay(x);
			v(x) = y;
			push_up(x);
		}
	}
	return 0;
}