[板子/笔记] Link Cut Tree

最近比较闲,来补补板子。
把Link Cut Tree这种神仙东西拉出来 讲(gāng)一讲(gāng)


Introduction

Link Cut Tree是解决动态树问题的一类数据结构。

将一棵树划分成许多重链,再用Splay(在这里称作这条链的辅助树)维护。

每棵Splay上的点按照原树上的深度作为权值。

辅助树的根R向它在原树上的父亲F连轻边,但这里轻边只有fa[R] = F而没有ch[F][] = R(认父不认子)

基础操作

下记节点x在辅助树的根是R(x),原树根是rt。

Access(x)

将rt-x的路径上的所有边都打成重链,再把原来经过路径上点的其他重边打成轻边。

具体做法是把x不断Splay(x)到根R(x)。再把右子树修改。

Makert(x)

将x变成原树的根。

首先Access(x),此时x是rt-x重链上深度最深的,在辅助树的最右,区间翻转就在最左,此时x深度最小,就成根了。

Find(x)

找x的原树根,用来判两点连通性。

Access(x)Splay(x)到根,查找深度最小的点,即沿左子树查下去即可。

Split(x,y)

拉出一条x到y的重链,辅助树以y做根。

Makert(x)Access(y),搞出x-y重链后再Splay(y)

将x连一条轻边向y。

Makert(x)后令fa[x] = y

Cut(x,y)

将x和y之间的边切断。

split(x,y)出重链x-y。

如果一定存在边(x,y),Makert(x)后x在原树上一定是y的父亲。dep[x] + 1 == dep[y]

x在辅助树上一定是y的左儿子。x,y一定连通。

同时,如果路径x-y上没有别的点,则x在辅助树上的右子树为空。

判好这三个条件就可以删边了:fa[x] = ch[y][0] = 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
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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
const int N = 300030;
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct LCT
{
int ch[N][2],fa[N],rev[N],sum[N],w[N];
inline int dc(int k){return ch[fa[k]][1] == k;}
inline int isrt(int k){return ch[fa[k]][0] != k && ch[fa[k]][1] != k;}
inline void pu(int k){sum[k] = sum[ch[k][0]] ^ sum[ch[k][1]] ^ w[k];}
inline void rever(int k){rev[k] ^= 1;std::swap(ch[k][0],ch[k][1]);}
inline void pd(int k)
{
if(rev[k])
{
if(ch[k][0]) rever(ch[k][0]);
if(ch[k][1]) rever(ch[k][1]);
rev[k] = 0;
}
}
inline void rpd(int k)
{
if(!isrt(k)) rpd(fa[k]);
pd(k);
}
inline void rot(int k)
{
int f = fa[k],ff = fa[f],d = dc(k);
fa[k] = ff;if(!isrt(f)) ch[ff][dc(f)] = k;
fa[ch[f][d] = ch[k][!d]] = f;
fa[ch[k][!d] = f] = k;
pu(f);pu(k);
}
inline void splay(int k)
{
rpd(k);
for(;!isrt(k);rot(k)) if(!isrt(fa[k])) rot(dc(fa[k]) == dc(k) ? fa[k] : k);
}
inline void access(int k)
{
for(int y = 0;k;y = k,k = fa[k])
{
splay(k);
ch[k][1] = y;
pu(k);
}
}
inline void makert(int k)
{
access(k);splay(k);rever(k);
}
inline int find(int k)
{
access(k);splay(k);
while(ch[k][0]) pd(k),k = ch[k][0];
return k;
}
inline void link(int x,int y)
{
makert(x);fa[x] = y;
}
inline void cut(int x,int y)
{
makert(x);access(y);splay(y);//亦可split(x,y),脑抽了qwq
if(fa[x] == y && !ch[x][1])fa[x] = ch[y][0] = 0;
pu(y);
}
inline void split(int x,int y)
{
makert(x);access(y);splay(y);
}
}T;
int main()
{
int n = getint(),m = getint();
for(int i = 1;i <= n;i++) T.w[i] = getint();
while(m--)
{
int opt = getint(),x = getint(),y = getint();
switch(opt)
{
case 0: T.split(x,y);printf("%d\n",T.sum[y]);break;
case 1: if(T.find(x) != T.find(y)) T.link(x,y);break;
case 2: if(T.find(x) == T.find(y)) T.cut(x,y);break;
case 3: T.w[x] = y;T.splay(x);break;
}
T.pt();
}
return 0;
}