Link Cut Tree学习笔记

Link-Cut Tree 是用于维护由一组有根树组成的森林的数据结构,Link-Cut Tree 的基本操作复杂度为均摊 $O({\log_2}n)$ ,具体的定义和时间复杂度的证明可以移步
《QTREE 解法的一些研究》,这里主要介绍它的基本操作的具体实现。

定义

1
2
3
4
5
6
7
8
9
struct node *null; //定义一个虚拟空节点
struct node {
node *fa, *c[2]; //fa 代表节点的父亲,c[2]代表节点的左右儿子
bool rev; //rev为翻转标记
node *top; //top代表节点所在实路径尾部节点的父亲
int siz;
node(): fa(null), top(NULL) {c[1] = c[0] = null;
//将每个点的父亲和左右儿子初始化为虚拟空节点,top为NULL
}

操作

Link-Cut Tree 支持以下几种基本操作:

1、 $Access(u)$,“访问”某个节点 u,被“访问”过的节点会与根节点之间以路径相连,并且该节点为路径头部(最下端);
2、 $Evert(u)$,将某个节点 u 置为其所在树的根节点,该操作等价于把该节点到根节点所经过的所有边方向取反;
3、 $Link(u, v)$,将某两个节点 u 和 v 连接;
4、 $Cut(u, v)$,将某两个节点 u 和 v 分离;
5、 $FindRoot(u)$,查找某个节点 u 所在树的根节点;

在实现这些操作之前,先列出基础操作

reverse

将一个节点翻转

1
2
3
4
inline void reverse () {
rev ^= 1;
swap(c[0], c[1]);
}

updata

更新节点信息

1
2
3
4
inline void updata() {
ma = max(max(c[1]->ma, c[0]->ma), val);
sum = c[1]->sum + c[0]->sum + val;
}

pushdown

标记下传

1
2
3
4
5
6
inline void pushdown() {
if (rev) {
c[1]->reverse(), c[0]->reverse();
rev = 0;
}
}

relation

得到节点是哪个儿子

1
2
3
inline bool relation() {
return fa->c[1] == this;
}

rotate

splay中的旋转操作,注意这里传递了一个bool值,用来表示将要旋转的这个节点是其父亲节点的哪个儿子。
注意在旋转时更新信息以及下传标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void rotate(const bool &f) {
node *o = fa;
top = o->top;
//保证top的有效值总在splay的根节点上
o->pushdown(), pushdown();
//下传标记
(fa = o->fa)->c[o->relation()] = this;
//将this的fa替换为o的fa,同时代替父亲成为o的fa的儿子
(o->c[f] = c[!f])->fa = o;
//因为this的c[!f]将变成o,所以this的c[!f]变成了o的c[f],同时更新它的fa
(c[!f] = o)->fa = this;
//o变成了this的c[f]
o->updata();
//更新o的值
}

splay

splay操作基本与普通的splay操作相同,注意标记下传和更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void splay() {
bool f;
node *o = fa;
for (pushdown(); o != null; o = fa) {
if (o->fa == null) {
rotate(o->c[1] == this);
} else {
(f = o->c[1] == this) == (o->fa->c[1] == o) ?
(o->rotate(f), rotate(f)) :
(rotate(f), rotate(!f));
}
}
updata();
}

access 操作

expose 操作

在实现 access 操作前,我们先来实现 expose 操作,它的作用是将当前节点置为其所在路径的头部节点,即切断自该节点向下的部分路径。

注意标记的下传和更新

1
2
3
4
5
6
7
8
9
10
inline void expose(node* p = null) {
splay();
if (c[1] != null) {
c[1]->fa = null;
c[1]->top = this;
}
(c[1] = p)->fa = this;
//若p为空,则右子树为空,否则将p所代表的树接在this的右子树位置
updata();
}

有了expose操作实现access操作就很简单了。

access 操作

先切断要access的节点的右子树(即切断自该节点向下的部分路径),然后若其所在实路径不包含根,则将当前节点所在的路径与其尾部节点的父节点所在的路径合并,即将路径的向上延长

1
2
3
4
5
6
inline void access() {
node *x = this;
for (x->expose(); x->top; x = x->top) {
x ->top->expose(x);
}
}

evert 操作

首先执行 Access,将该节点与根节点之间用一条完整的路径连接,然后翻转这条路径即可。

1
2
3
inline void evert() {
access(); splay(); reverse();
}

把它变成根然后把top设置成this就好辣

1
2
3
4
inline void link(node *y) {
y->evert();
y->top=this;
}

cut 操作

因为这两个点是连在一起的,所以expose一下,再把top断开就好了

1
2
3
4
5
6
inline void cut(node *y) {
node *x = this;
x->expose(), y->expose();
if (x->top == y) x->top = NULL;
if (y->top == x) y->top = NULL;
}

findroot 操作

access一下,在splay树上找到最左边的儿子,即是这个实路径的尾部节点,同时也是树根,找的时候传一下标记。

1
2
3
4
5
6
7
inline node* findroot() {
node *f = this;
f->access(), f->splay();
while (f->pushdown(), f->c[0] != null)f = f->c[0];
f->splay();
return f;
}

query 和 modify 操作

以查询两个点之间的点权最大值为例。首先在 Node 结构体中存储 max 成员,并在 updata( )中维护它。

首先,如果需要查询某个点到根节点之间的点权最大值,只需先访问这个节点,即 access(u),然后对该节点执行 splay 操作,将其置为其所在splay 的根节点,此时 u 的 max 存储的值即为 u 到其所在树的根节点的路径上的点权最大值。

如果要查询任意两点间的点权最大值,只需要先对其中一个节点执行 evert 操作,将其置为树根,就可以转化为上述情况进行处理。

split 操作

要查询两点间路径上的值,先把一个点置为根,然后查询就好了

1
2
3
4
inline void split(node *y) {
y->evert(); access(); splay();
//此时this节点的值就代表了这一段路径上的值
}

路径上修改也是同理,先split一下,修改this的值,然后打上标记就好辣

要修改某个点的点权值,只需要对该节点执行 splay 操作,将其置为其所在 splay 的根节点,然后直接修改即可,这样可以避免修改时标记的向上传递。

modify操作(单点)

1
2
3
4
5
inline void modify(const int &v) {
splay();
val = v;
updata();
}

init操作

对虚拟空节点进行初始化,可以根据具体题目要求进行更改

1
2
3
4
5
inline void init() {
null = pool;
null->fa = null->c[1] = null->c[0] = null;
null->siz = 0;
}

例题

一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一:

  • u v c:将u到v的路径上的点的权值都加上自然数c;
  • u1 v1 u2 v2:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树;
  • u v c:将u到v的路径上的点的权值都乘上自然数c;
    / u v:询问u到v的路径上的点的权值和,求出答案对于51061的余数。

    链接

    bzoj-2631

输入

第一行两个整数n,q
接下来n-1行每行两个正整数u,v,描述这棵树
接下来q行,每行描述一个操作

输出

对于每个/对应的答案输出一行

样例

输入

1
2
3
4
5
3 2
1 2
2 3
* 1 3 4
/ 1 1

输出

1
4

数据规模和约定
$10\%$的数据保证,$1<=n,q<=2000$
另外$15\%$的数据保证,$1<=n,q<=510^4$,没有$-$操作,并且初始树为一条链
另外$35\%$的数据保证,$1<=n,q<=5
10^4$,没有$-$操作
$100\%$的数据保证,$1<=n,q<=10^5,0<=c<=10^4$

题解

LCT随便搞搞就好了,模板题

代码

其中的常数优化和读入输出优化参考了xehoth的代码

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
184
185
#include <bits/stdc++.h>
using namespace std;
struct node* null;
const int mod = 51061;
const int N = 100011;
struct node {
node *fa, *c[2];
bool rev;
node *top;
unsigned int siz, sum, add, mul, val;
node(): siz(1), sum(1), val(1), mul(1), fa(null) {
c[0] = c[1] = null;
}
inline void cover(const int &m, const int &a) {
val = (val * m + a) % mod;
sum = (sum * m + a * siz) % mod;
add = (add * m + a) % mod;
mul = mul * m % mod;
}
inline void updata() {
sum = (c[0]->sum + c[1]->sum + val) % mod;
siz = (c[0]->siz + c[1]->siz + 1) % mod;
}
inline void reverse() {
rev ^= 1;
swap(c[1], c[0]);
}
inline void pushdown() {
if (rev) {
c[0]->reverse(), c[1]->reverse(), rev = 0;
}
if (add != 0 || mul != 1) {
c[0]->cover(mul, add), c[1]->cover(mul, add);
mul = 1, add = 0;
}
}
inline bool relation() {
return fa->c[1] == this;
}
inline void rotate(const bool f) {
node *o = fa;
top = o->top;
o->pushdown(), pushdown();
(fa = o->fa)->c[o->relation()] = this;
(o->c[f] = c[!f])->fa = o;
(c[!f] = o)->fa = this;
o->updata();
}
inline void splay() {
bool f;
node *o = fa;
for (pushdown(); o != null; o = fa) {
if (o->fa == null) {
rotate(o->c[1] == this);
} else {
(f = o->c[1] == this) == (o->fa->c[1] == o)
? (o->rotate(f), rotate(f)) : (rotate(f), rotate(!f));
}
}
updata();
}
inline void expose(node * p = null) {
splay();
if (c[1] != null) {
c[1]->top = this;
c[1]->fa = null;
}
(c[1] = p)->fa = this;
updata();
}
inline void access() {
node *x = this;
for (x->expose(); x->top; x = x->top)
x->top->expose(x);
}
inline void evert() {
access(); splay(); reverse();
}
inline void link(node *y) {
y->evert();
y->top = this;
}
inline void cut(node *y) {
node *x = this;
x->expose(), y->expose();
if (x->top == y) x->top = NULL;
if (y->top == x) y->top = NULL;
}
inline node* findroot() {
node *f = this;
f->access(), f->splay();
while (f->pushdown(), f->c[0] != null)f = f->c[0];
f->splay();
return f;
}
inline void split(node *y) {
y->evert(); access(); splay();
}
} pool[N];
inline void init() {
null = pool;
null->fa = null;
null->mul = 1;
null->add = null->siz = null->val = null->sum = 0;
}
inline char nextChar() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
inline int read() {
static int x = 0;
static char c;
for (x = 0, c = nextChar(); !isdigit(c); c = nextChar());
for (; isdigit(c); c = nextChar())
x = (x + (4 * x) << 1) + (c ^ '0');
return x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *oh = obuf;
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
*oh++ = '0';
} else {
if (x < 0) *oh++ = '-', x = -x;
register int cnt = 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) *oh++ = buf[cnt--];
}
}
template<class T>
inline void println(T x) {
print(x), *oh++ = '\n';
}
inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}
int n, q;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
init();
n = read(), q = read();
for (register int i = 1; i <= n; i++) pool[i] = node();
char s;
register int x, y, z;
for (register int i = 1; i < n; i++) (pool + read())->link(pool + read());
for (register int i = 1; i <= q; i++) {
s = nextChar(), x = read(), y = read();
switch (s) {
case '+':
z = read(), (pool + x)->split(pool + y);
(pool + x)->cover(1, z);
break;
case '-':
(pool + x)->cut(pool + y),
x = read(), y = read(),
(pool + x)->link(pool + y);
break;
case '*':
z = read(), (pool + x)->split(pool + y);
(pool + x)->cover(z, 0);
break;
case '/':
(pool + x)->split(pool + y), println((pool + x)->sum);
break;
}
}
flush();
return 0;
}

文章目录
  1. 1. 定义
  2. 2. 操作
    1. 2.0.1. 在实现这些操作之前,先列出基础操作
  3. 2.1. reverse
  4. 2.2. updata
  5. 2.3. pushdown
  6. 2.4. relation
  7. 2.5. rotate
  8. 2.6. splay
  • 3. access 操作
    1. 3.1. expose 操作
    2. 3.2. access 操作
  • 4. evert 操作
  • 5. link 操作
  • 6. cut 操作
  • 7. findroot 操作
  • 8. query 和 modify 操作
    1. 8.1. split 操作
    2. 8.2. modify操作(单点)
  • 9. init操作
  • 例题
    1. 1. 链接
    2. 2. 输入
    3. 3. 输出
    4. 4. 样例
      1. 4.1. 输入
      2. 4.2. 输出
    5. 5. 题解
    6. 6. 代码