【学习笔记】LCT初步

一种以 $ \rm Splay $ 作为辅助树的、动态维护森林连通性的算法。

$ \rm{0x01} $ 闲话 · $\rm LCT$ 的用途以及具体思路

咳,其实在我最近只是浅浅地学了一部分的基础上,窝觉得 $\rm LCT$ 其实就是一个用来维护森林连通性的。

嗯……因为其独特的性质所以也可以顺便维护好多东西,什么链上的最大值啊,链上的权值和啊……都可以维护——或者说,$\rm LCT$ 是更加全能的树剖。

但其实吧…… $ \rm LCT $ 打板子是很简单的,但是真正理解却一点儿也不简单。因为本身 $\rm splay$ 就很麻烦了,况且 $\rm splay$ 之前一直用于维护数列。要知道,此处的 $\rm splay$ 可是作为辅助树,维护一整个森林,并且可以支持序列中几乎全部操作——这就大大增高了理解难度。举个例子,你曾经认为已经难以理解、或者说不可以做的、比较复杂的区间翻转 $\rm Luogu3391 $ ,在 $\rm LCT$ 里面有十分全面的涉及,但是被精简到了只有两行是用来描述这个内容的。显而易见的是, $\rm LCT $ 虽然常数十分的大,但代码十分的短,比一棵完整的平衡树短了不少(实测50+行),与 $ \rm FFT $ 一样具有着华丽的可观赏性,但是隐藏在之后的思维难度同样不可小觑。

也就是说我们是不是学的太草率、太浮躁了呢?快餐式地学完 $\rm LCT$ ,网上的每一篇博客都包教包会。但是我今天要整理的,是对于 $ \rm LCT $ 真正的理解。希望各位看到这篇拙作的人可以获得一些什么。

$ \rm{0x02} $ 闲话 · 关于 $ \rm{splay} $

道理我都懂,要想动态拆删一些东西,辅助树的形态可以改变是先决条件。看上去平衡树好像是个不错的选择,但是,选哪个作为辅助树呢?后宫佳丽三千我该翻谁的牌子呢

历史的重任最后落到了 $ \rm{splay} $ 的身上。然后 $ \rm{splay} $ 他居然:

他甚至还:

……

好吧,由于某些rqy也不知道的原因,如果不用 $ \rm{splay} $ 的话,复杂度是均摊 $ \Theta(\rm{nlog^2n}) $ , 而用 $ \rm{splay} $ 就可以做到均摊 $ \Theta(\rm{nlogn}) $ ……但事实上,splay确实有他独特的性质,比如旋转到根啊之类的,比起其他种类的平衡树而言,更加适合 $\rm LCT$

$ \rm{0x03} $ $\rm LCT$ 的思路和基础操作

一 主要思路

主要思路嘛……大概是基于实链剖分的操作。

朴素的树剖是重链剖分,大体上就是将整棵树的链划分为轻边和重链,运用巧妙的性质做到 $ log $ 级别。而遗憾的是 $\rm LCT$ 维护的是森林的连通性,所以只能采用实链剖分。

而实链剖分大体上就是把边分为虚边实边。其中实边串联起一个联通块,同一组实边存在、且仅存在于一棵 $ \rm{splay} $ 中。 $ \rm{splay} $ 和 $ \rm{splay} $ 之间由虚边相连。

实链剖分的好处呢?在于实链剖分是一种动态剖分,他可以随意改变边的虚实属性。而显然,重链剖分由于有着足够的理论依据和逻辑推演,所以轻重链是难以更改,或者说,不可更改的。So,实链剖分为动态树的动态打下了基础。

那么接下来我们来看一个 $\rm LCT$ 是如何定义的:

  • 0、本质上, $\rm LCT$ 是一堆树,正如它的全称「$\rm Link-Cut~Trees$」,里面充斥着实边和虚边。每一棵单独的 $\rm Link-Cut ~Tree$ 用来维护一个连通块(原图中连通)。

  • 1、首先,一棵 $\rm LCT$ 管控的是一堆分散的点,点以几棵分散的 $\rm splay$ 的形式聚集。起初整棵 $\rm LCT$ 是没有任何联系的,各自为战,各自为根。接下来看到的 $ access $ 、 $ makeroot $ 等操作,都是在自己的联通块儿内部进行的操作。换句话讲, $\rm LCT$ 维护的是有根森林,即组成森林的每个联通块都有其唯一的根。

  • 2、实边串联起一个联通块,同一组实边存在、且仅存在于一棵 $ \rm{splay} $ 中。 $ \rm{splay} $ 和 $ \rm{splay} $ 之间由虚边相连。只有实边是有效的,虚边可以被认为不存在。但是两种边都没有用到显式存储,都是通过splay中的 $ Son $ 数组和 $ Fa $ 数组访问的。但虚边和实边的存储有区别:

  • 3、虚边是认父不认子,即如果 $ Fa[x]==y $ ,那么 $ y $ 不存 $ x $ 这个儿子,但是 $ x $ 存 $ y $ 这个父亲。这样做是为了可以 $ Access $ ——因为其实在 $ Access $ 的子函数 $\rm splay$ 里,发挥作用的实际上是 $ Fa $ 指针。

  • 4、实边是完整的双向存储。

  • 5、显然的是, $ \rm{splay} $ 中维护的是一条从上到下按在原树中深度严格递增的路径,且中序遍历 $ \rm{splay} $ 得到的每个点的深度序列严格递增。换句话讲,一个 $ \rm{splay} $ 里面不会出现在原联通块儿(树)中深度相同的两个点。在一棵 $ \rm{splay} $ 中,键值就是原树中的深度。

  • 6、如果 $ x $ 是它所在 $\rm splay$ 的最左边的点,那么它在原森林里的父亲是 $ x $ 所在 $\rm splay$ 的根的 $ fa $ , 否则就是 $ x $ 在 $\rm splay$ 上的前驱。

二 基础操作

$ emm $ 所谓基础操作大概就是每个用到 $\rm LCT$ 的题几乎都要用到的操作。我们把 $ n $ 以实边相连的儿子记作实儿子,否则记为虚儿子。

同时值得注意的是,$\rm Access$、$\rm Make~Root$ 、$\rm Find~Root$ 和 $\rm Merge$ 操作都是针对一棵 $lct$ 的操作,而 $\rm Link$ 和 $\rm Cut$ 则是针对一整片 $lct$ 森林,可以看做“分裂/合并两个 $\rm LCT$”。

至于连通块的根,可以看做是给无根树强行钦定的一个根,即原图里的根(似乎可以结合并查集理解?

Access

这个操作有着很迷的性质,其时间复杂度是均摊 $ \log n $ 的。而这个操作的目的是 $ Access(n) $ 表示从 $ root $ 向 $ n $ 打通一条实链,并以 $ n $ 点为最深度最大的点、 $ root $ 为深度最小的点形成一棵 $ \rm{splay} $

不难看出,这个操作其实就是把原来 $\rm splay$ 的割据给改变了。

我们思考,如果此时我们 $ Access $ 完点 $ n $ 之后,理论上来讲, $ n $ 点应该不再有实儿子了——显然,如果有实儿子的话, $\rm splay$ 中是应该包含这个实儿子的——而这就不符合 $ n $ 是 $ \rm{splay} $ 中深度最大的点的性质了。而因为在 $ \rm splay $ 中,点是以深度为键值的,所以我们要每次砍掉 $ \rm{splay} $ 中的右儿子——即砍掉原来的实儿子,并把刚刚诞生的 $ \rm{splay} $ 连上。

1
2
3
4
inline void Access(int x) { 
for (int qwq = 0 ; x ; x = T[qwq = x].F)
splay(x), rc = qwq, update(x) ;
}

然后这就是 $\rm Access $ 了。

Make Root

这个操作的目的是把一个节点变成 $ lct$ 的根节点。

先从 $ root $ 向 $ n $ 打通一条路径,然后 $\rm splay$ 上去,最后 $ reverse $ 一下。此处由于一开始 $ n $ 的深度最大, $\rm splay$ 之后深度依旧最大,但此时 $ n $ 是 $\rm splay$ 的根,所以 $ reverse(n) $ 就相当于翻转了整条树上的链,那么翻转之后, $ n $ 的深度就变成了最小,于是就是这个联通块儿的根节点了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define lc T[x].Son[0]
#define rc T[x].Son[1]
struct LCT{
int F, Son[2], R, S ;
}T[MAXN] ;
void splay(int x) ;
void reverse(int x) { lc ^= rc ^= lc ^= rc, T[x].R ^= 1 ;}
void push_down(int x) { if (!T[x].R) return ; T[x].R = 0 ; if (lc) reverse(lc) ; if (rc) reverse(rc) ; }

void Rooten(int x) { Access(x), splay(x), reverse(x) ; }

void splay(int x){
int qwq = x ; stk.push(qwq) ;
while(check(qwq)) qwq = T[qwq].F, stk.push(qwq) ;
while(!stk.empty()) push_down(stk.top()), stk.pop() ;
while(check(x)){
int fa = T[x].F, g_fa = T[fa].F ;
if (check(fa)) rotate((T[g_fa].Son[1] == fa) == (T[fa].Son[1] == x) ? fa : x) ; rotate(x) ;
}

此处 $\rm splay$ 中由于要下放标记,需要保证树的形态是正确的,所以我们用一个 $ stack $ 存一下,顺序下放标记。

Merge

此处的 $\rm Merge(x, y) $ 的意义是,拉起 $ x,y $ 中间的链,形成一个 $\rm splay$ 。这里就直接 $ Mkroot $ 一遍,然后 $ Access $ 即可。让哪个点当根应该都可以,只不过多 $\rm splay$ 几次可以保证优(毒)秀(瘤)的复(大)杂(常)度(数)。

upd:此处 $\rm splay$ 还有深层次的意图,就是可以保证现在 $ x $ 和 $ y $ 是相邻的,这样在cut的时候就会很方便了。

1
void Merge(int x, int y) { Rooten(x), Access(y), splay(y) ; }

如果保证 $ \rm Link $ 和 $ \rm Cut $ 都是合法的操作的话, $ \rm Link $ 直接连, $ \rm Cut $ 直接删即可。

1
2
void Link(int x, int y){ Rooten(x) ; T[x].F = y ;}
void Cut(int x, int y){ Merge(x, y) ; T[x].F = T[y].Son[0] = 0 ;}

此处 $\rm Link$ 必须先 $ \rm Mkroot $ 一下,否则树链就断了。连的是虚边(因为连实边就会改变原来 $\rm splay$ 的割据); $ \rm Cut $ 必须先 $\rm Merge$ 一下,保证两个点之间在同一棵 $\rm splay$ 中,加之我们的 $ Merge $ 操作中,一开始把 $ x $ 给 $ mkroot $ 了,再把 $ y $ 点 $\rm splay$ 上去,直接导致了现在 $ x $ 应该是 $ y $ 的孩子——于是就很开心的,可以直接 $\rm Cut$ 了。

但事实上,天不遂人意……有时候这条边并不存在,盲目删除的话会导致 $ GG $ ,盲目连边的话也会导致树的形态爆炸,所以我们要进行一波操作……

1
2
void Link(int x, int y){ Rooten(x) ; if(Find(y) != x) T[x].F = y ;}
int Find(int x){ Access(x), splay(x) ; while(lc) push_down(x), x = lc ; splay(x) ; return x ;}

此处的意义在于,如果我们发现两个点在一个子树里面,连接它们就破坏了树的性质。 $ \rm Find $ 则是找到这个 $lct$ 维护的连通块内的根。

但要注意啊, $ Find $ 找的是原树中的根,不是 $\rm splay$ 。由于原树中根的深度一定最小,所以应该是 $\rm splay$ 中最靠左的点……所以不断找左儿子。

多 $ BB $ 一句,这个地方一定注意啊! $ Find $ 只改变了 $\rm splay$ 的形态, $ mkroot $ 改变的是原树中的根

New-Cut

1
2
3
4
5
void Cut(int x, int y){ 
Rooten(x) ;
if (Find(y) != x || T[y].Son[0] || T[y].F != x) return ;
T[y].F = T[x].Son[1] = 0, update(x) ;
}

此处首先我们要判一下这两个点是不是直接相连。是否直接相连……在一棵 $\rm splay$ 中的体现,要克服两个问题,第一是要判断是否连通,还是 $ Find $ 操作。

之后我们需要判断是否满足恰好相隔一条边——注意,首先因为代码中的 $ x $ 比 $ y $ 在原树位置靠上( $ Rooten $ 了 $ x $ ),在 $\rm splay$ 中靠左,那么如果 $ y $ 有左儿子的话,说明一定有

其中 $\rm depth$ 表示原树深度。那么此时原树中 $ x $ 和 $ y $ 之间,一定隔着一些节点。考虑树的性质,两点之间有且仅有一条简单路径——所以当 $\rm T[y].son[0] $ 不指向 $ Null $ 时, $ x $ 和 $ y $ 之间没有一条边,不能直接 $\rm Cut$ 。

剩下的就很简单了, $\rm T[y].F $ 应该是 $ x $ ,否则也不是直接相连。

Rotate 中的坑点

呃……其实就一处而已。就是:

1
2
3
4
5
6
7
bool check(int x){ return T[T[x].F].Son[0] == x || T[T[x].F].Son[1] == x ;  }
void rotate(int x) {
int fa = T[x].F, g_fa = T[fa].F, W = x == T[fa].Son[1] ;
if (check(fa)) T[g_fa].Son[T[g_fa].Son[1] == fa] = x ; T[x].F = g_fa ;
T[fa].Son[W] = T[x].Son[W ^ 1], T[T[x].Son[W ^ 1]].F = fa, T[fa].F = x ;
T[x].Son[W ^ 1] = fa, update(fa), update(x) ;
}

这个地方 $\rm splay$ 双旋判断祖父的时候,不再用 $ \rm{if(g\text{_}fa)} $ ,而是用 $ \rm{if(check(fa))} $ 。原因很简单,我们的虚边也是有指向父亲的指针的,但是连接两个不同的 $\rm splay$

剩下的……大概就没了吧……

于是——

$ \color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e} $

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//题目名称:UOJ#3 「NOI2014」魔法森林
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define il inline
#define rg register
#define gcr getchar
#define fr(k) E[k].fr
#define to(k) E[k].to
#define va(k) E[k].va
#define vb(k) E[k].vb
#define fa(x) t[x].fa
#define rv(x) t[x].rev
#define lc(x) t[x].son[0]
#define rc(x) t[x].son[1]

using namespace std ;

const int N = 200010 ;
const int M = 400010 ;
const int MAX = 1000000008 ;

struct LCT{
int fa ;
bool rev ;
int son[2] ;
}t[N] ;
struct Edge{
int va, vb ;
int fr, to ;
}E[M] ;
int ans ;
int n, m ;
int f[N] ;
int sz[N] ;
int val[N] ;
int stk[N], tp ;

il bool comp(Edge a, Edge b){
return a.va < b.va ;
}
il bool notroot(int x){
return (lc(fa(x)) == x) || (rc(fa(x)) == x) ;
}
il void reverse(int x){
rv(x) ^= 1 ; swap(lc(x), rc(x)) ;
}
il void update(int x){
val[x] = x ;
if (vb(val[x]) < vb(val[lc(x)])) val[x] = val[lc(x)] ;
if (vb(val[x]) < vb(val[rc(x)])) val[x] = val[rc(x)] ;
}
il void _down(int x){
if (rv(x)){
rv(x) = 0 ;
if (lc(x)) reverse(lc(x)) ;
if (rc(x)) reverse(rc(x)) ;
}
}
il void rotate(int x){
int w = x == rc(fa(x)) ;
int f1 = fa(x), f2 = fa(f1) ;
if (notroot(f1))
t[f2].son[f1 == rc(f2)] = x ;
fa(x) = f2 ; fa(f1) = x ;
fa(t[x].son[w ^ 1]) = f1 ;
t[f1].son[w] = t[x].son[w ^ 1] ;
t[x].son[w ^ 1] = f1 ;
update(f1), update(x) ;
}
il void splay(int x){
int y ;
stk[++ tp] = y = x ;
while (notroot(y))
y = fa(y), stk[++ tp] = y ;
while (tp) _down(stk[tp --]) ;
while (notroot(x)){
int f1 = fa(x) ;
int f2 = fa(f1) ;
if (notroot(f1)){
if ((f1 == rc(f2)) == (rc(f1) == x))
rotate(f1) ; else rotate(x) ;
}
rotate(x) ;
}
}
il void qr(int &x){
x = 0 ; char c = gcr() ;
while (c > '9' || c < '0') c = gcr() ;
while (isdigit(c)) x = x * 10 + c - 48, c = gcr() ;
}
il void access(int x){
int y = 0 ;
for ( ; x ; x = fa(y = x))
splay(x), rc(x) = y, update(x) ;
}
il int find_root(int x){
access(x) ; splay(x) ;
while (lc(x)) x = lc(x) ;
return x ;
}
il void make_root(int x){
access(x) ;
splay(x) ; reverse(x) ;
}
il void link(int x, int y){
make_root(x) ;
if (find_root(y) != x)
return fa(x) = y, void() ;
}
il void split(int x, int y){
make_root(x) ;
access(y) ; splay(y) ;
}
il void cut(int x){
access(to(x)) ; splay(x) ;
lc(x) = rc(x) = fa(lc(x)) = fa(rc(x)) = 0 ;
update(x) ;
}
il int Min(const int &x, const int &y){
return x < y ? x : y ;
}
int find(int x){
return x == f[x] ? x : f[x] = find(f[x]) ;
}
int main(){
cin >> n >> m ; ans = MAX ;
for (int i = 1 ; i <= m ; ++ i)
qr(fr(i)), qr(to(i)), qr(va(i)), qr(vb(i)) ;
for (int i = 1 ; i <= m ; ++ i) fr(i) += m, to(i) += m ;
for (int i = 1 ; i <= n + m + 1 ; ++ i) f[i] = i ;
sort(E + 1, E + m + 1, comp) ;
for (int i = 1 ; i <= m ; ++ i){
rg int f1, f2 ;
rg int u = fr(i), v = to(i) ;
if (u == v) continue ;
//cout << val[i] << endl ;
split(v, u) ;
f1 = find(u), f2 = find(v) ;
//cout << f1 << " " << f2 << endl ;
if (f1 != f2){
link(u, i), link(v, i) ;
if (sz[f1] < sz[f2])
f[f1] = f2, sz[f2] += sz[f1] ;
else f[f2] = f1, sz[f1] += sz[f2] ;
}
else if (vb(i) < vb(val[u]))
cut(val[u]), link(u, i), link(v, i) ;
if (find(m + 1) == find(m + n))
split(m + 1, n + m),
ans = Min(ans, va(i) + vb(val[n + m]) ) ;
}
cout << (ans == MAX ? -1 : ans) << endl ; return 0 ;
}

后记和参考

可写完了……嗝……打个肥宅嗝犒劳犒劳自己

怎么说呢,自从我开始学 $\rm LCT$ 到我写完这篇 $ blog $ 为止,是我十分难熬的时间,总时长接近一周。一开始看别人写的 $\rm LCT$ ,想当然地、草率地理解了理解,就开始打板子,对 $\rm LCT$ 一直是极为肤浅的认识。直到开始写,才发现自己哪个地方都不会,理解的半生不熟,总之很惨……

写博客真是一个陶冶情操的过程啊……包括做表情包

加油吧, $ pks $ !

$ \rm{Reference} $

$ \mathfrak{writter:pks} $