目录

  1. 引言
  2. 目录
  3. 讲解
    1. Link-Cut-Tree基础
      1. 讲解
      2. 模板
      3. 例题
      4. 易错点
      5. 后记
    2. Link-Cut-Tree维护边信息
      1. 讲解
      2. 模板
      3. 例题
      4. 易错点
      5. 后记
    3. Link-Cut-Tree维护子树信息
      1. 讲解

引言

终于迎来这一刻啦O(∩_∩)O~,可以专心致志地写一篇完全解析了

先理一下先修知识

先修知识:

  • 树链剖分
  • Splay平衡树
  • Splay翻转树

再介绍一下本文的目录

目录

  • Link-Cut-Tree基础

    • 讲解
    • 模板
    • 例题
    • 易错点
  • Link-Cut-Tree维护边信息

    • 讲解
    • 模板
    • 例题
    • 易错点
  • Link-Cut-Tree维护子树信息

    • 讲解
    • 模板
    • 例题
    • 易错点
  • Link-Cut-Tree高级应用

    • 前言
    • 例题
    • 易错点

当然,这只是期望的样子,要真的完成这么多恐怕要好长时间吧

讲解

那么,讲解就正式开始啦!

讲解

首先,大家应该都学习过树链剖分对吧,我们知道,树链剖分维护的是一个固定的树剖分,我们通常采用轻重树链剖分法来实现这一点,但是,当树的形态可以发生改变的时候,这么做显然就不行了,因为如果我们继续使用当前的链剖分形式,就无法保证时间复杂度,而如果动态地去维护树剖分,听起来又好像是一件挺困难的事情

实际上,我们正是采用后者进行维护的,这个东西,就是传说中的动态树了,而维护树的形态改变以后的新的树剖分的算法,就是这次的主要内容Link-Cut-Tree

我们知道,一个树剖分是由链组成的,而对于每一条链来说,这就是一个序列,而对于序列上的问题,我们可以采用许多方法进行解决,比如使用数据结构

在树链剖分里面,我们正是这样做的,我们先求出一个树剖分,然后把它们放到线段树上进行统一的维护,这样就大大地降低了算法的复杂度和维护的难度。但是,对于动态树来说,它的形态在不断的发生变化,这样,我们很难记录每条链的顶端等信息,然后使用线段树维护

这样,由于有了序列的动态操作,所以我们需要一种支持快速的序列分裂与合并操作的数据结构,这让我们想到Splay

而Link-Cut-Tree正是采用了这样的方法,我们把每条链都放到一棵Splay上进行维护,然后进行某种操作

既然是用Splay来维护,那么Splay本身的操作就很自然地加入到了Link-Cut-Tree中,所以,我们首先需要实现如下操作:

  • is_root(x)操作,判断x是否已经是Splay的根
1
2
3
inline bool is_root(int x){
return (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
}
  • pushup(x)操作,把儿子信息上传到当前点
1
2
3
inline void pushup(int x){
siz[x] = siz[ls] + siz[rs] + 1;//此处维护了子树大小
}
  • pushdown(x)操作,把当前点标记下传给儿子
1
2
3
4
5
6
7
inline void pushdown(int x){
if (rev[x]){
swap(ls, rs);
rev[ls] ^= 1, rev[rs] ^= 1;
rev[x] = 0;
}
}
  • rotate(x)操作,旋转平衡树的核心操作——旋转,此处不解释
1
2
3
4
5
6
7
8
9
10
11
12
13
inline void rotate(int x){
int k = x;
x = fa[x];
int d = ch[x][1] == k;
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
  • splay(x)操作,Splay的核心操作——伸展,把某一个点“伸展”到根,其实就是旋转到根的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int st[maxn];
int cst = 0;
void splay(int x){
int t = x;
while (!is_root(x)){
st[++cst] = x;
x = fa[x];
}
st[++cst] = x;
while (cst){
pushdown(st[cst]);
cst--;
}//为了方便我们事先pushdown所有会经过的结点
x = t;
while (!is_root(x)){
int f1 = fa[x];
if (!is_root(f1)){
int f2 = fa[f1];
if ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
}
rotate(x);
}
}

然后,我们再对常见的树上形态改变操作进行逐个分析:

  • Link(x, y)操作,连接两个不同点

如果直接合并两棵树,那么就可能会导致两棵树的父子关系不匹配(或者说树的方向不一致,可以自行体会)

我们发现,如果要调整父子关系体系使得这两棵树匹配的话,只需要调整其中的一棵就可以,而且为了理顺父子关系,我们肯定需要让连到另一棵树上的这个点成为自己所在树的根,然后连上去

这个操作就是moveroot

所以,我们现在需要实现moveroot,具体该怎么做呢?我们可以分析这个操作,我们需要让这个点先一路连到根,使它和根在同一条链里,也就是同一棵Splay里,然后,我们知道,点的深度决定了点在Splay里的键值,由于我们把一个点设置为根,相当于把这个点到根的路径的深度翻转,也就是把链翻转

而把链翻转,其实就是序列翻转,而这个正好是Splay的标志性操作,我们就可以在Splay中直接翻转这个序列

这样的话,我们在Splay就需要维护反转标记,下传时需要交换左右儿子

但是我们发现,如果我们直接合并所有的从x到根的链,那么会导致一些原来在x下方的点也被包含了进来,这样的话,就会变得比较麻烦,因为这些点是不需要被翻转的,如果保留它们,在最后打翻转标记的时候就需要分裂Splay,那我们不妨一开始就舍弃他们,这样便没有了后顾之忧

这个合并到根路径上所有链形成新的链的操作就是access

先说一句,合并所有链,指的是在一条链被合并的时候,它不在这条路径上的部分是会被舍弃的,也就是说,我们最后合并完的东西,还是一条链,并且一端为x,另一端为根

在这个操作中,我们需要不断的合并、分裂Splay,但是,我们发现,永远被合并、分裂的部分的深度是从链的底端向上的一部分,而合并也是从底端向下接上一端,这些恰好与Splay合并、分裂不相交序列的经典操作吻合(总之Splay无限好,看起来就像是专门为了LCT开发的……),所以我们只需要直接在Splay上操作就可以了,代码如下:

1
2
3
4
5
6
7
8
9
10
void access(int x){
int tem = 0;
while (x){
splay(x);
rs = tem;
pushup(x);
tem = x;
x = fa[x];
}
}

具体来说就是不断先把当前点旋到根,然后连接上新的右子树,然后爬向父亲,如此往复直到原树树根

这样,我们解决了access操作

回到moveroot,我们显然是要先进行一次access,然后翻转这棵Splay,那么这个也是Splay基础操作,我们把要打标记的那个点Splay到根,然后直接打上反转标记即可

1
2
3
4
5
void moveroot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}

这样moveroot也解决了

回到Link操作,我们也就是需要把其中一个点x设置为根,即moveroot(x),然后直接把它连到另一个点上,即fa[x] = y,由于每个点维护的是Splay树中的信息,而x与y之间的边不在Splay中,所以不必更新y的任何信息(但是后文要讲的就不是这样(^_^) ……)

1
2
3
4
void link(int x, int y){
moveroot(x);
fa[x] = y;
}

这样Link操作就被我们解决了

还有一个操作,因为既然有Link,那么一定有Cut对吧,这样才是Link-Cut-Tree嘛

Cut还要用到一个额外的操作,但是一会再说…

  • Cut(x, y)操作,断开x与y在原树上的连接

我们先假设x与y之间存在这条边

我们发现,我们很难直接Cut掉两个点之间的连接,因为它们要么在同一棵Splay里,要么不在,如果在的话,由于我们把链放在了Splay中,所以它们之间不一定有边相连,位置关系也很难确定,不在一棵Splay中则更是如此

那么,我们首先要做的,是舍弃不在同一棵Splay中的情况,就是把它们两个放在一条链里,而我们现在有的操作,只有moveroot和access,能不能通过这两个操作实现这一目的呢?这是可以的

我们先moveroot(y),然后access(x),这样x,y就很自然地在同一条链上了

那么,在同一条链上以后呢?此时x, y在Splay里面的位置关系是未知的,我们要把情况归一来方便处理,那么我们可以splay(x),这样就整洁多了

由于x, y之间有边,y还是树根,那么x左子树里肯定只有一个点,那就是y,这时候,我们就可以放心的断开这条边啦,即fa[y] = ch[x][0] = 0,但是因为这样做改变了Splay的形态,所以我们需要对x进行一下pushup(x)操作

1
2
3
4
5
void cut(int x, int y){
split(x, y);
fa[y] = ls = 0;
pushup(x);
}

下面只剩下最后的一个部分啦,那就是链修改与查询的相关操作,无论是哪一种,为了正确地处理问题,我们都需要单独将这条链提取出来,其实就是直接类比Splay里面的修改与查询,这样,我们就还需要一种操作,那就是提取特定链

  • split(x, y)操作,将x到y的链提取出来放进一棵Splay中维护,并且为了处理修改与查询,使x为Splay的根

这样,我们需要做的,就是把x, y放进一棵Splay,等等,这个和刚才Cut时的操作有点像啊?

其实就是一个操作,我们先moveroot(y),然后access(x),最后再splay(x),这就是split(x, y)的全部操作

1
2
3
4
5
void split(int x, int y){
moveroot(y);
access(x);
splay(x);
}

所以,Cut中的操作,事实上是先提取链,然后断开连接

这样,我们每次修改与查询的时候,直接作用于被操作链的Splay根就可以了,因为这棵Splay本身就是这条被操作链

下面再讲一个东西,就是高鲁棒性的Link-Cut-Tree操作:

有的时候,我们会Link两个已经连通的点,此时我们需要忽略此操作(后文有些时候就不会忽略),还有的时候,我们会Cut两个没有边直接相连的点,这时我们也需要忽略,那么这样该怎么做呢?

我们再加入一个操作:

  • check(x, y)操作,检查两个点是否已经连通

具体做法应该很简单了吧,我们直接access(x),然后splay(x),然后一直向左跳找到原树树根,对y也这样做,然后看这两个树根是否相同即可

1
2
3
4
5
6
7
8
9
bool check(int x, int y){
access(x); splay(x);
while (ls) x = ls;
int f1 = x;
x = y;
access(x); splay(x);
while (ls) x = ls;
return f1 == x;
}

但是常常会有另一种写法,那就是直接从这个点开始暴力跳父亲,跳到树根,这样好像也挺正确的

实际上,我们最好不要这样写,虽然这样比较简便,但是这样做实际上是无法获得复杂度保证的,是一种错误的写法(个人认为)

关于LCT的复杂度,下面会提到

然后,对于Link,我们事先check一下x, y就可以了

1
2
3
4
5
void link(int x, int y){
if (check(x, y)) return;
moveroot(x);
fa[x] = y;
}

对于Cut,我们也是要先Check一下,但是两个点即使在同一棵树里也不一定有边直接相连,所以,我们需要在split(x, y)以后,判断y的左右儿子是否存在,只要有一个存在,都是需要直接return掉的

1
2
3
4
5
6
7
void cut(int x, int y){
split(x, y);
if (ls == y && !ch[y][0] && !ch[y][1]){
fa[y] = ls = 0;
pushup(x);
}
}

至于为什么,可以自己思考一下

关于LCT的复杂度证明,首先用到的是Splay的均摊复杂度证明,这个可以证明是$O(\log n)$的,然后,对于LCT的access操作来说(因为别的操作都由此衍生,所以只分析这个就可以了),可以证明是一种差分相加的形式,最后可以势能分析仍然是$O(\log n)$的,这也就解释了为什么我认为暴力跳父亲是错误写法,因为这样失去了势能分析的前提条件

模板

汇总一下,板子大概就是这个样子的:

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
int ch[maxn][2];
int val[maxn];
int sum[maxn];
int fa[maxn];
bool rev[maxn];
bool is_root(int x){
return (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
}
void pushup(int x){
sum[x] = sum[ls] + sum[rs] + val[x];
}
void pushdown(int x){
if (rev[x]){
swap(ls, rs);
rev[ls] ^= 1, rev[rs] ^= 1;
rev[x] = 0;
}
}
void rotate(int x){
int k = x;
x = fa[x];
int d = ch[x][1] == k;
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
int st[maxn];
int cst = 0;
void splay(int x){
int t = x;
while (!is_root(x)){
st[++cst] = x;
x = fa[x];
}
st[++cst] = x;
while (cst){
pushdown(st[cst]);
cst--;
}//为了方便我们事先pushdown所有会经过的结点
x = t;
while (!is_root(x)){
int f1 = fa[x];
if (!is_root(f1)){
int f2 = fa[f1];
if ((ch[f1][1] == x) ^ (ch[f2][1] == f1)) rotate(x);
else rotate(f1);
}
rotate(x);
}
}
void access(int x){
int t = 0;
while (x){
splay(x);
rs = t;
pushup(x);
t = x;
x = fa[x];
}
}
void moveroot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}
void split(int x, int y){
moveroot(y);
access(x);
splay(x);
}
bool check(int x, int y){
access(x); splay(x);
while (ls) x = ls;
int f1 = x;
x = y;
access(x); splay(x);
while (ls) x = ls;
int f2 = x;
return f1 == f2;
}
void link(int x, int y){
if (check(x, y)) return;
moveroot(x);
fa[x] = y;
}
void cut(int x, int y){
split(x, y);
if (ls == y && !ch[y][0] && !ch[y][1]){
fa[y] = ls = 0;
pushup(x);
}
}
void modify(int x, int y){
splay(x);
val[x] = y;
}
int get(int x, int y){
split(x, y);
return sum[x];
}

这个有两种操作,一个是单点修改,一个是链查询

例题

既然都讲到这里了,那就放几道例题吧,一句话题解采用白色字体

易错点

  • pushdown操作中,除了交换子树以外不可以将信息延迟更新,比如链加操作,必须在接收到add标记以后就立刻更新sum, mx, mi等信息,而rev标记不需要,但是如果rev标记也采用这种及时更新信息的方法,那么注意是否交换子树不取决于当前的rev标记,而在于传递的标记值

  • 如果有Splay的其他操作,比如找第K大这种需要从根向下游历的操作,必须沿路进行pushdown操作,因为不这样做无法保证左右子树的正确性和信息正确性。这种错误往往非常隐蔽,一定要小心!

  • 在Splay中进行了查询某个点的操作以后,为了保证时间复杂度,必须将这个点Splay到根,这其实是Splay的有关内容,在那个里面也算是一个易错点吧

  • 在注意Splay中预先pushdown时,最后到根的那个点也要加入栈中,而且在Splay时,不能因为当前点已经是根就直接不执行Splay操作,因为这样会影响access中的子树交换正确性

  • 寻找当前原树树根的方法必须采用上文讲述的方法

  • 注意Splay中每次需要rotate的点

  • 注意pushup的时候要算上自己的信息

  • rotate时需要判断被rotate的点的父亲是否为Splay的根

  • 注意题目中对Link, Cut操作鲁棒性的要求

后记

那么,本章就到此结束啦!对于LCT来说,把基本的概念理解的十分透彻是一件十分重要的事,因为所有的LCT题目都离不开对基本结构的理解与分析

讲解

我们都知道,树上不只是有点,还是有边的,而边上往往也会负载许多的信息,比如长度什么的

在树链剖分中,我们常用的做法是把边信息下放到深度较大的那一端上,这样是正确的,而且维护起来十分方便

但是在LCT中,由于父子关系时常发生变化,所以,这样做很难维护正确性,我们必须考虑使用其他的方法

既然LCT维护点信息十分方便,那么我们为什么不将边信息转化为点信息呢?考虑到图论中常用的加点法,我们可以把每一条边都看成点,然后这个新点向原来的两端连边,然后,我们把边信息附着在这个点上,我们就可以维护边信息啦

当然,还有不用加点的方法,在neither_nor的博客中被提到了,那个方法比较复杂,所以像我这么菜肯定是不会的啦O(∩_∩)O!

其实就是这么点东西……

这样,我们就可以解决许多的问题了,比如动态最小生成树,线段树分治套最小生成树……之类的

模板

有一道十分经典的题目,那就是[Noi2014]魔法森林这道题,相信很多人都是使用什么动点SPFA这种暴力的方法过的是吧……

我们就以它为例吧!

具体方法大家是不是都会……

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <stack>
#define maxn 300005
#define INF 2000000005
#define ls ch[x][0]
#define rs ch[x][1]
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
struct edge{
int x, y, va, vb;
edge(int x = 0, int y = 0, int va = 0, int vb = 0) : x(x), y(y), va(va), vb(vb){}
}e[maxn << 1];
bool cmp(edge a, edge b){
return (a.va != b.va) ? a.va < b.va : a.vb < b.vb;
}
int ch[maxn][2];
int mx[maxn];
int val[maxn];
int fa[maxn];
bool rev[maxn];
stack<int> s;
void pushup(int x){
mx[x] = x;
if (val[mx[ls]] > val[mx[x]]) mx[x] = mx[ls];
if (val[mx[rs]] > val[mx[x]]) mx[x] = mx[rs];
}
void pushdown(int x){
if (rev[x]){
rev[ls] ^= 1, rev[rs] ^= 1;
swap(ls, rs);
rev[x] = 0;
}
}
bool is_root(int x){
return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}
void rotate(int x, int d){
int k = ch[x][d];
fa[k] = fa[x];
if (!is_root(x)) ch[fa[x]][ch[fa[x]][1] == x] = k;
ch[x][d] = ch[k][d ^ 1];
fa[ch[x][d]] = x;
ch[k][d ^ 1] = x;
fa[x] = k;
pushup(x);
pushup(k);
}
void splay(int x){
int tem = x;
while (!is_root(x)){
s.push(x);
x = fa[x];
}
s.push(x);
while (!s.empty()){
pushdown(s.top());
s.pop();
}
x = tem;
while (!is_root(x)){
int f1 = fa[x];
int d1 = ch[f1][1] == x;
if (!is_root(f1)){
int f2 = fa[f1];
int d2 = ch[f2][1] == f1;
if (d1 ^ d2) rotate(f1, d1), rotate(f2, d2);
else rotate(f2, d2), rotate(f1, d1);
}
else rotate(f1, d1);
}
}
void access(int x){
int tmp = 0;
while (x){
splay(x);
rs = tmp;
pushup(x);
tmp = x;
x = fa[x];
}
}
void moveroot(int x){
access(x);
splay(x);
rev[x] ^= 1;
}
void split(int x, int y){
moveroot(y);
access(x);
splay(x);
}
void link(int x, int y){
moveroot(x);
fa[x] = y;
}
void cut(int x, int y){
split(x, y);
fa[y] = ls = 0;
pushup(x);
}
int get_max_point(int x, int y){
split(x, y);
return mx[x];
}
bool check(int x, int y){
access(x), splay(x);
while (ls) x = ls;
int f1 = x;
x = y;
access(x), splay(x);
while (ls) x = ls;
return f1 == x;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("magic.in", "r", stdin);
#endif
int x, y, z, w;
read(n), read(m);
rep(i, 1, m){
read(x), read(y), read(z), read(w);
e[i] = edge(x, y, z, w);
}
//rep(i, 1, n) val[i] = 0;
sort(e + 1, e + 1 + m, cmp);
rep(i, 1, m) val[i + n] = e[i].vb;//Link-Cut-Tree上维护的是B的有关信息
int ans = INF;
rep(i, 1, m){
x = e[i].x, y = e[i].y, z = e[i].va, w = e[i].vb;
if (!check(x, y)) {
link(x, i + n);
link(y, i + n);
}
else{
int k = get_max_point(x, y);
if (val[k] > w) {
cut(k, e[k - n].x);
cut(k, e[k - n].y);
link(x, i + n);
link(y, i + n);
}
}
if (check(1, n)){
int k = get_max_point(1, n);
ans = min(ans, val[k] + z);
}
}
if (ans == INF) printf("-1");
else printf("%d", ans);
return 0;
}

例题

易错点

  • 最主要的易错点,就是由于加点而引起的点数增多,这常常会被忽略而导致严重的问题,我们要时刻考虑这个问题

后记

这就是一个常用的技巧,其实没什么难的……

讲解

不错,终于到了这里了~

这个技巧是相对来说有点难度的(其实也没有……),我们知道LCT本身其实是很难维护子树信息的,因为它的维护对象是树上的链剖分,也就是一条一条的链

我们发现,一个点的子树,会包含什么?

显然这个点在某个链剖分上,所以,它一定会包含自己所在链的下面的点的各自的子树,以及它自己的不在链上的子树

这样,我们可以子树信息分为三部分,一个是实子树信息,就是Splay上的LCT子树信息,另一个是虚子树信息,就是自己的不在链上的点的LCT子树信息,第三个,就是前面提到的LCT子树信息,一个点的LCT子树信息,就是它的实子树信息与虚子树信息之和

看起来比较乱是不是

我们发现,一个点如果不是链上的最底端的点,那么它所包含的也会有自己下面的链上的其他点的信息,而这样是很难维护的,我们要做的就是把这个点下面的链上点都与他断开

  • 模板
  • 例题
  • 易错点
  • Link-Cut-Tree高级应用
    • 前言
    • 例题
    • 易错点