Link-Cut Tree 是一种用来维护动态森林连通性的数据结构,适用于动态树问题。它采用类似树链剖分的轻重边路径剖分,把树边分为实边和虚边,并用 Splay 来维护每一条实路径。Link-Cut Tree 的基本操作复杂度为均摊 ,但常数因子较大,一般效率会低于树链剖分。
定义
一棵 Link-Cut Tree 上的边分为两种:实边和虚边。每一种边都是有向的,由子节点指向父节点。首尾相连的实边组成的不可延伸的链叫做路径。路径中深度最大的节点称为路径头部,深度最小的节点称为路径尾部。
将每一条路径上的节点按照深度排序,得到一个序列,用 Splay 来维护这个序列。
每一条链对应着一棵 Splay,每棵 Splay 的根节点有一个成员 Path Parent
,表示该 Splay 维护的路径的尾部的节点的父节点,整棵树的根节点所对应的 Splay 节点的 Path Parent
为空;其他节点(不是其所在 Splay 的根节点的节点)的 Path Parent
也为空。
value
用于维护点权,sum
和 max
是根据题目要求维护的链上的区间信息。reversed
表示以该节点为根的 Splay 有没有被翻转。
struct Node {
Node *child[2], *parent, *pathParent;
T value, sum, max;
bool reversed;
}
操作
Link-Cut Tree 支持以下几种基本操作:
Access(u)
,“访问”某个节点u
,被“访问”过的节点会与根节点之间以路径相连,并且该节点为路径头部(最下端);Evert(u)
,将某个节点u
置为其所在树的根节点,该操作等价于把该节点到根节点所经过的所有边方向取反;Link(u, v)
,将某两个节点u
和v
连接,执行操作后u
成为v
的父节点;Cut(u, v)
,将某两个节点u
和v
分离,执行操作后v
及其子节点组成单独的一棵树;FindRoot(u)
,查找某个节点u
所在树的根节点;MakeTree()
,向森林中种植一棵新的树。
Access
操作
Expose
操作
在实现 Access
操作前,我们先来实现 Expose
操作,它的作用是将当前节点置为其所在路径的头部节点,即切断自该节点向下的部分路径。
- 将该节点
Splay
到其所在 Splay 的根节点; - 如果该节点有右孩子,那么断开其与其右孩子的连接。
不要忘了各种标记的下放和值的维护。
void expose() {
splay();
pushDown();
if (child[R]) {
child[R]->parent = NULL;
child[R]->pathParent = this;
child[R] = NULL;
maintain();
}
}
Splice
操作
接下来,我们来实现 Splice
操作,它的作用是将当前节点所在的路径与其尾部节点的父节点所在的路径合并,即实现了路径的向上延长。
- 将该节点
Splay
到其所在 Splay 的根节点; - 如果该节点没有
Path Parent
,那么说明该节点所在路径中包含根节点,即Splice
操作失败。 - 对该节点的
Path Parent
执行Expose
操作,将其原有的路径断开; - 将该节点连接到其
Path Parent
的右孩子上,并将Path Parent
置为空。
bool splice() {
splay();
if (!pathParent) return false;
pathParent->expose();
pathParent->child[R] = this;
parent = pathParent;
pathParent = NULL;
parent->maintain();
return true;
}
Access
操作
有了 Expose
和 Splice
,Access
就简单多了,Expose
后执行 Splice
直到失败即可。
void access() {
expose();
while (splice());
}
Evert
操作
首先执行 Access
,将该节点与根节点之间用一条完整的路径连接,然后翻转这条路径即可。
void evert() {
access();
splay();
reversed ^= 1;
}
Link
操作
将节点 v
置为其所在树的根,然后将其 Path Parent
置为节点 u
即可。
void link(int u, int v) {
nodes[v - 1]->evert();
nodes[v - 1]->pathParent = nodes[u - 1];
}
Cut
操作
Cut
操作稍微复杂一点:
- 将节点
u
置为其所在树的根节点,以保证v
是u
的子节点; - 对
v
执行Access
操作,将v
与u
之间用一条完整的路径连接; - 对
v
执行Splay
操作,将v
置于其所在 Splay 的根节点; - 将
v
与其左子树分离,即将路径断开。
void cut(int u, int v) {
nodes[u - 1]->evert();
nodes[v - 1]->access();
nodes[v - 1]->splay();
nodes[v - 1]->pushDown();
nodes[v - 1]->child[L]->parent = NULL;
nodes[v - 1]->child[L] = NULL;
nodes[v - 1]->maintain();
}
Query
和 Update
操作
以 QueryMax(u, v)
查询两个点之间的点权最大值为例。首先在 Node
结构体中存储 max
成员,并在 Maintain()
中维护它。
首先,如果需要查询某个点到根节点之间的点权最大值,只需先访问这个节点,即 Access(u)
,然后对该节点执行 Splay
操作,将其置为其所在 Splay 的根节点,此时 u
的 max
存储的值即为 u
到其所在树的根节点的路径上的点权最大值。
如果要查询任意两点间的点权最大值,只需要先对其中一个节点执行 Evert
操作,将其置为树根,就可以转化为上述情况进行处理。
const T &Node::queryMax() {
access();
splay();
return max;
}
const T &queryMax(int u, int v) {
nodes[u - 1]->evert();
return nodes[v - 1]->queryMax();
}
要修改某个点的点权值,只需要对该节点执行 Splay
操作,将其置为其所在 Splay 的根节点,然后直接修改即可,这样可以避免修改时标记的向上传递。
void update(int u, const T &value) {
nodes[u - 1]->splay();
nodes[u - 1]->value = value;
nodes[u - 1]->maintain();
}
MakeTree
操作
直接新建节点就可以。
void makeTree(int u, const T &value) {
nodes[u - 1] = new Node(value);
}
其他操作 & 注意事项
- 进行
Splay
和Rotate
时,要注意标记的传递; Rotate
时,需要将自己的Path Parent
与父节点的Path Parent
互换,以保证Path Parent
成员的有效值总在一棵 Splay 的根节点上。
void pushDown() {
if (reversed) {
std::swap(child[L], child[R]);
if (child[L]) child[L]->reversed ^= 1;
if (child[R]) child[R]->reversed ^= 1;
reversed = false;
}
}
void maintain() {
sum = value;
if (child[L]) sum += child[L]->sum;
if (child[R]) sum += child[R]->sum;
max = value;
if (child[L]) max = std::max(max, child[L]->max);
if (child[R]) max = std::max(max, child[R]->max);
}
void rotate() {
if (parent->parent) parent->parent->pushDown();
parent->pushDown(), pushDown();
std::swap(pathParent, parent->pathParent);
Relation x = relation();
Node *oldParent = parent;
if (oldParent->parent) oldParent->parent->child[oldParent->relation()] = this;
parent = oldParent->parent;
oldParent->child[x] = child[x ^ 1];
if (child[x ^ 1]) child[x ^ 1]->parent = oldParent;
child[x ^ 1] = oldParent;
oldParent->parent = this;
oldParent->maintain(), maintain();
}
void splay() {
while (parent) {
if (!parent->parent) rotate();
else {
parent->parent->pushDown(), parent->pushDown();
if (relation() == parent->relation()) parent->rotate(), rotate();
else rotate(), rotate();
}
}
}
完整代码(树的统计)
#include <cstdio>
#include <climits>
#include <algorithm>
const int MAXN = 30000;
void print(void *p);
template <typename T>
struct LinkCutTree {
enum Relation {
L = 0, R = 1
};
struct Node {
Node *child[2], *parent, *pathParent;
T value, sum, max;
bool reversed;
Node(const T &value) : reversed(false), value(value), sum(value), max(value), parent(NULL), pathParent(NULL) {
child[L] = child[R] = NULL;
}
Relation relation() {
return this == parent->child[L] ? L : R;
}
void pushDown() {
if (reversed) {
std::swap(child[L], child[R]);
if (child[L]) child[L]->reversed ^= 1;
if (child[R]) child[R]->reversed ^= 1;
reversed = false;
}
}
void maintain() {
sum = value;
if (child[L]) sum += child[L]->sum;
if (child[R]) sum += child[R]->sum;
max = value;
if (child[L]) max = std::max(max, child[L]->max);
if (child[R]) max = std::max(max, child[R]->max);
}
void rotate() {
if (parent->parent) parent->parent->pushDown();
parent->pushDown(), pushDown();
std::swap(pathParent, parent->pathParent);
Relation x = relation();
Node *oldParent = parent;
if (oldParent->parent) oldParent->parent->child[oldParent->relation()] = this;
parent = oldParent->parent;
oldParent->child[x] = child[x ^ 1];
if (child[x ^ 1]) child[x ^ 1]->parent = oldParent;
child[x ^ 1] = oldParent;
oldParent->parent = this;
oldParent->maintain(), maintain();
}
void splay() {
while (parent) {
if (!parent->parent) rotate();
else {
parent->parent->pushDown(), parent->pushDown();
if (relation() == parent->relation()) parent->rotate(), rotate();
else rotate(), rotate();
}
}
}
void evert() {
access();
splay();
reversed ^= 1;
}
void expose() {
splay();
pushDown();
if (child[R]) {
child[R]->parent = NULL;
child[R]->pathParent = this;
child[R] = NULL;
maintain();
}
}
bool splice() {
splay();
if (!pathParent) return false;
pathParent->expose();
pathParent->child[R] = this;
parent = pathParent;
pathParent = NULL;
parent->maintain();
return true;
}
void access() {
expose();
while (splice());
}
const T &querySum() {
access();
splay();
return sum;
}
const T &queryMax() {
access();
splay();
return max;
}
};
Node *nodes[MAXN];
void makeTree(int u, const T &value) {
nodes[u - 1] = new Node(value);
}
void link(int u, int v) {
nodes[v - 1]->evert();
nodes[v - 1]->pathParent = nodes[u - 1];
}
void cut(int u, int v) {
nodes[u - 1]->evert();
nodes[v - 1]->access();
nodes[v - 1]->splay();
nodes[v - 1]->pushDown();
nodes[v - 1]->child[L]->parent = NULL;
nodes[v - 1]->child[L] = NULL;
nodes[v - 1]->maintain();
}
const T &querySum(int u, int v) {
nodes[u - 1]->evert();
return nodes[v - 1]->querySum();
}
const T &queryMax(int u, int v) {
nodes[u - 1]->evert();
return nodes[v - 1]->queryMax();
}
void update(int u, const T &value) {
nodes[u - 1]->splay();
nodes[u - 1]->value = value;
nodes[u - 1]->maintain();
}
};
struct UndirectedEdge {
int u, v;
UndirectedEdge() {}
UndirectedEdge(int u, int v) : u(u), v(v) {}
} edges[MAXN - 1];
int n, q;
LinkCutTree<int> lct;
void dfs(LinkCutTree<int>::Node *v, int depth) {
if (!v) return;
dfs(v->child[LinkCutTree<int>::L], depth + 1);
for (int i = 0; i < depth; i++) putchar(' ');
printf("%d, max = %d, sum = %d\n", v->value, v->max, v->sum);
dfs(v->child[LinkCutTree<int>::R], depth + 1);
}
void print(void *p) {
dfs((LinkCutTree<int>::Node *)p, 0);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
edges[i] = UndirectedEdge(u, v);
}
for (int i = 1; i <= n; i++) {
int value;
scanf("%d", &value);
lct.makeTree(i, value);
}
for (int i = 0; i < n - 1; i++) {
lct.link(edges[i].u, edges[i].v);
}
scanf("%d", &q);
for (int i = 0; i < q; i++) {
char str[6 + 1];
scanf("%s", str);
if (str[1] == 'H') {
int u, t;
scanf("%d %d", &u, &t);
lct.update(u, t);
} else if (str[1] == 'M') {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", lct.queryMax(u, v));
} else if (str[1] == 'S') {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", lct.querySum(u, v));
}
}
return 0;
}