学习笔记：Link Cut Tree

模板题

原理

类似树链剖分对重儿子/长儿子剖分，Link Cut Tree 也做的是类似的链剖分。

每个节点选出 (0 / 1) 个儿子作为实儿子，剩下是虚儿子。对应的边是实边/虚边，虚实时可以进行灵活变换的。

实链：实边连起来的极大链，也可以理解为所有实边构成的若干联通块。

Splay 维护每个实链，其中中序遍历对应着从上到下维护的路径：

  1. 本质上是维护所有实边，用 Splay 中的后继前驱来维护原树的父子关系。
  2. 如何维护虚边的父子呢？即实链之间的关系，认父不认子。设 ((u, v)) 是一条边，(x) 是 (v) 所在 Splay 的根，发现 (x) 在 Splay 上的 (fa) 还没用过，所以维护在 Splay 的根上 (fa) 就是原路径上端的点。即 (fa_x = v)，但 (v) 的儿子中没有 (x)，这是重点。（这是重点。一般人理解的都是 (fa_v = u)，但实际上是错的。）

我们可以理解为，实边是双向互通的关系，虚边是单向关系。

这样的话原树和 Splay 树可以做到对应，所以只需要维护辅助 Splay 树就可以了。

前置 / 简单信息：

  1. 数组
const int N = 100005; // 点数
int ch[N][2], f[N], rev[N];
// ch[p][0 / 1] -> p 的左右儿子
// f[p] -> p 的父亲
// rev[p] -> p 的翻转标记
#define ls ch[p][0]
#define rs ch[p][1]
  1. (pushup(p)) 更新信息
void inline pushup(int p) {
    // 用 p 的儿子来维护 p 的信息
}
  1. (reverse(p)) 区间翻转（LCT必备，因为接下来的 (makeRoot) 函数需要支持翻转操作）
void inline reverse(int p) {
    if (!p) return;
    rev[p] ^= 1, swap(ls, rs);
}
  1. (pushdown(p)) 下传标记
void inline pushdown(int p) {
    if (rev[p]) {
        reverse(ls); reverse(rs);
        rev[p] = 0;
    }
    // 做一些其他的下传标记.jpg
}
  1. (update(p)) 由于我们在做某些操作时不一定是从根到 (p) 走过，可能还没有 (pushdown)，所以要把根到 (p) 的路径一路 (pushdown)。
void update(int p) {
	if (!isRoot(p)) update(f[p]);
	pushdown(p);
}
  1. (isRoot(x)) ：(x) 是不是当前 Splay 的根，如果父亲不指向 (x) 就是根。
#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

一些操作：

  1. (rotate(x)) 把 (x) 向上旋转。

注意，不同于原 Splay 的是，(z) 的儿子赋值为 (x) 这步一定要在 (y) 的 (fa) 信息改变之前，原因就是要判断 (y) 是不是根才需要赋值 (z) 的儿子信息，不能让 (y) 的信息改变。

PS：图中的 (2, 1) 节点分别对应着 (x, y)。

img

void inline rotate(int x) {
    int y = f[x], z = f[y], k = get(x);
    if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
    ch[y][k] = ch[x][!k], f[ch[y][k]] = y;
    ch[x][!k] = y, f[y] = x, f[x] = z;
    pushup(y), pushup(x);
}
  1. (splay(x)) 把 (x) 旋转到根。

img

记住一条链先转 (f_x)，然后转 (x)；有翻折转两次 (x) 就行，注意这么转的意义是保证 Splay 的那个势能复杂度是对的。

注意事先要 (update(p))，且终止条件是 (isRoot(p))。

void inline splay(int p) {
	update(p);
	for (int fa = f[p]; !isRoot(p); rotate(p), fa = f[p]) {
		if (!isRoot(fa)) rotate(get(p) == get(fa) ? fa : p);
	}
}
  1. (access(x)) 当且仅当拉一条从根到 (x) 的路径，强制让 (x) 没有实儿子。换句话说，就是让根所在的 Splay 当且仅当只有跟到 (x) 的路径上这些点。

盗了网上的图：

pic2

pic3

从下到上去做，每次迭代：

  • (splay(x)) 把 (x) 旋转到根，此时 (y = fa_x) 就是需要连接的上面一个实链

  • (splay(y))，赋值 (y) 的右儿子是 (x)，这样就成功切换了实儿子，因为原先 (y) 右儿子是原先树 (y) 下面的点，把它全部替换成 (x)，就切换了实边。

迭代到根就可以了~

inline int access(int x) {
	int p = 0;
	for (p = 0; x; p = x, x = f[x]) {
		splay(x), ch[x][1] = p, pushUp(x);
	}
	return p;
}
  1. (makeRoot(x)) 把 (x) 变成其所在原树的根节点，等于一个换根。即让 (x) 到当前根的父子关系全部翻转，(access(x)) 当且仅当把根到 (x) 的路径拉出来后，等价于 Splay 中把这颗 Splay 整体 reverse，所以就需要 (splay(x)) 后在 (x) （现在 (x) 是 Splay 的根），打一个翻转标记，你发现在二叉树上打翻转标记，他的中序遍历正好也被 reverse 了。（简要的证明一下，任意位置 (ABC) 的中序遍历都会变成 (CBA) 结构然后无限递归下去，这样显然中序遍历正好相反，正好达到目标）
void makeRoot(int p) {
	access(p), splay(p);
	reverse(p);
}
  1. (find(x)) 找到 (x) 所在原树的根节点。等于找到当前 splay 的最小键，(access(x)) 且 (splay(x)) 一直往左走就可以了。
int find(int p) {
	access(p), splay(p);
	while (ls) pushdown(p), p = ls;
	splay(p);
	return p;
}
  1. (split(x, y)) 将 (x, y) 的路径变为实边路径（具体地，将 (y) 变成所在 Splay 的根，当前 Splay 仅包含 (x, y) 之间路径上的点，想拿信息直接从 (y) 节点上拿就可以）：(makeroot(x), access(y), splay(y))。
void split(int x, int y) {
	makeRoot(x), access(y), splay(y);
}
  1. (link(x, y)) 若 (x, y) 不连通，则 ((x, y)) 连边。(makeroot(x))，如果 (findroot(y) ot= x)，那么 (fa_x = y) 就行了。
void link(int x, int y) {
	makeRoot(x);
	if (find(y) != x) f[x] = y;
}
  1. (cut(x, y)) 若 (x, y) 之间有边就去掉。(split(x, y)) 后，(x, y) 有边当且仅当 (x) 是 (y) 的前驱（并且由于双向连边，所以充要条件是 (x) 是 (y) 的左儿子，并且 (x) 没有右儿子（即判定前驱关系的成立）），判一下，如果是直接双向断边。
void cut(int x, int y) {
	split(x, y);
	if (ch[y][0] == x && !ch[x][1]) ch[y][0] = 0, f[x] = 0;
}

例题

【模板】Link Cut Tree （动态树）

#include <iostream>
#include <cstdio>
#define ls ch[p][0]
#define rs ch[p][1]
#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)
#define get(x) (ch[f[x]][1] == x)
using namespace std;

const int N = 100005;

int n, m;
int ch[N][2], rev[N], f[N], val[N], dat[N];

void inline pushup(int p) {
	dat[p] = dat[ls] ^ val[p] ^ dat[rs];
}

void inline reverse(int p) {
	if (!p) return;
	rev[p] ^= 1, swap(ls, rs);
}

void inline pushdown(int p) {
	if (rev[p]) {
		reverse(ls); reverse(rs);
		rev[p] = 0;
	}
}

void update(int p) {
	if (!isRoot(p)) update(f[p]);
	pushdown(p);
}

void inline rotate(int x) {
	int y = f[x], z = f[y], k = get(x);
	if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
	ch[y][k] = ch[x][!k], f[ch[y][k]] = y;
	ch[x][!k] = y, f[y] = x, f[x] = z;
	pushup(y), pushup(x);
}

void inline splay(int p) {
	update(p);
	for (int fa = f[p]; !isRoot(p); rotate(p), fa = f[p]) {
		if (!isRoot(fa)) rotate(get(p) == get(fa) ? fa : p);
	}
}

int inline access(int p) {
	int x = 0;
	for (; p; x = p, p = f[p]) {
		splay(p), ch[p][1] = x, pushup(p);
	}
	return x;
}

void makeRoot(int p) {
	access(p), splay(p);
	reverse(p);
}

int find(int p) {
	access(p), splay(p);
	while (ls) pushdown(p), p = ls;
	splay(p);
	return p;
}

void link(int x, int y) {
	makeRoot(x);
	if (find(y) != x) f[x] = y;
}

void split(int x, int y) {
	makeRoot(x), access(y), splay(y);
}

void cut(int x, int y) {
	split(x, y);
	if (ch[y][0] == x && !ch[x][1]) ch[y][0] = 0, f[x] = 0, pushup(y);
}


int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", val + i), dat[i] = val[i];
	while (m--) {
		int opt, x, y; scanf("%d%d%d", &opt, &x, &y);
		if (opt == 0) split(x, y), printf("%d
", dat[y]);
		else if (opt == 1) link(x, y);
		else if (opt == 2) cut(x, y);
		else splay(x), val[x] = y, pushup(x);
	}
	return 0;
}

NOI2014 魔法森林

把边按 (a) 从小到大排序，每次枚举一个 (i)，用 (1 sim i) 这些边，即用 (le a_i) 的边，找出 (1 - n) 最小瓶颈路（(b) 为边权）。那么每次需要维护动态加入一个边，很像 Link Cut Tree，但如何加出来有环怎么办，即去掉最大的 (b) 的边就可以了（瓶颈路的性质）。

需要支持：

  1. 连边
  2. 两点之间最大边权

边权转点权的技巧，每个边加一个新点。

就可以了~

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/dmoransky/p/13833317.html