连接切割树

2024-01-17

学习笔记

5.1k 词

Link Cut Tree 可以用来维护动态树（树的形态会变化，支持加边删边）的信息。

实链剖分

对于树上每个节点连向儿子的所有边，任意选择至多一条进行剖分。我们称选择的边为实边，连接的儿子为实儿子，其余边为虚边，连接的儿子为虚儿子。

实际上就是任意剖分，因为是任意的所以可以由我们随意改变以满足动态树的要求。

辅助树

对于每一条实链都建一棵 Splay，其中序遍历是该链上点按深度从小到大排序。然后对于每棵 Splay，其根向该实链顶的父亲连一条虚边，这条虚边与 Splay 上的边的区别在于虚边认父不认子，即无法从父亲通过虚边访问儿子。

容易发现可以通过辅助树还原出原树，因此我们只需要维护辅助树而不需要维护原树。

例子：

原树为：

辅助树为：

（图源 OI Wiki）

节点信息

对于辅助树上每个节点，因为是 Splay，所以需要维护父亲 $fa$ ，左右儿子 $son _ {0 / 1}$ ，子树大小 $siz$ 。下面会讲到需要支持 reverse 操作，因此需要维护翻转标记 $swp$ ，以及题目要求的信息。

以上信息在代码中分别记为 fa，son[0]，son[1]，siz，swp。

基础操作

pushup / pushdown

更新节点信息。

void pushup(int now) {
	siz[now] = siz[son[now][0]] + siz[son[now][1]] + 1;
	// Update other Information.
	return ;
}
void pushdown(int now) {
	if(!swp[now]) return ;
	swap(son[now][0], son[now][1]);
	swp[son[now][0]] ^= 1, swp[son[now][1]] ^= 1;
	swp[now] = 0;
	// Update other Information.
	return ;
}

isRoot

判断当前节点是否是其所在 Splay 的根。

1	int isRoot(int now) {return now != son[fa[now]][0] && now != son[fa[now]][1];}

get / rotate / splay

Splay 的基本操作， $get(x)$ 获取 $x$ 是左儿子还是右儿子， $rotate(x)$ 将点 $x$ 往上旋转， $splay(x)$ 将点 $x$ 转到当前 Splay 的根。

int get(int now) {return now == son[fa[now]][1];}
void rotate(int x) {
	int y = fa[x], z = fa[fa[x]], chk = get(x);
	if (!isRoot(y)) son[z][get(y)] = x;
	son[y][chk] = son[x][chk ^ 1], fa[son[x][chk ^ 1]] = y;
	son[x][chk ^ 1] = y, fa[y] = x;
	fa[x] = z;
	pushup(y), pushup(x);
	return ;
}
void splay(int now) {
	vector<int> stk;
	stk.push_back(now);
	for (int i = now; !isRoot(i); i = fa[i]) stk.push_back(fa[i]);
	while (!stk.empty()) pushdown(stk.back()), stk.pop_back();
	// 在旋转之前将路径上所有点的标记都下传
	for (int f; f = fa[now], !isRoot(now); rotate(now))
		if (!isRoot(f)) rotate(get(f) == get(now) ? f : now);
	return ;
}

access

$access$ 函数是 LCT 的核心，作用是将一个点 $x$ 与根“打通”，即将其与根放到同一条实链中，并且 $x$ 是这条实链的末尾。

首先 $splay(x)$ ，然后该 Splay 中 $x$ 的右子树即为这条实链 $x$ 以下的部分，直接将其断掉。

然后不断往上跳实链，将上面一条实链从与当前实链顶端连接处断开（方法与上面相同），然后再将这两棵 Splay 合并即可。

void access(int now) {
	for (int lst = 0; now; lst = now, now = fa[now]) splay(now), son[now][1] = lst, pushup(now);
	return ;
}

makeRoot

$makeRoot(x)$ 的功能是时 $x$ 成为这棵树的根。
先 $access(x)$ 再 $splay(x)$ ，这样 $x$ 就变成了这棵 Splay 的根，并且没有右儿子。然后将整棵 Splay reverse 即可。

1	void makeRoot(int now) {access(now); splay(now); swp[now] ^= 1; return ;}

维护信息

link / cut

$link(u, v)$ 的功能是连接 $(u, v)$ 。
$makeRoot(u)$ ，然后将 $fa _ u$ 设为 $v$ 即可。

1	void link(int u, int v) {makeRoot(u); fa[u] = v; return ;}

$cut(u, v)$ 则是切断 $(u, v)$ 这条边。
$makeRoot(u)$ ，然后 $access(v)$ ，此时得到一棵仅有 $u, v$ 的 Splay， $splay(v)$ 后切断 $u, v$ 之间的边即可。

1	void cut(int u, int v) {makeRoot(u); access(v); splay(v); son[v][0] = fa[u] = 0; return ;}

find

$find(x)$ 的功能是找到 $x$ 所在树的根。
$access(x)$ ，然后根就是所在 Splay 最左侧的点。

注意为了保证复杂度，找到根后需要对其进行 $splay$ 操作。

int find(int now) {
	access(now), splay(now);
	pushdown(now);
	while (son[now][0]) now = son[now][0], pushdown(now);
	splay(now);
	return now;
}

split

为了维护一条链的信息，我们需要将其打通，并且需要他是实链。 $split(u, v)$ 可以将 $u$ 变成根并得到一棵仅包含 $u, v$ 这条链的 Splay 以满足我们的要求。

1	void split(int u, int v) {makeRoot(u); access(v); splay(u); return ;}

链修改 / 查询

对于一条端点为 $u, v$ 的链的修改 / 查询，只要 $split(u, v)$ 即可。

判断两个点是否在同一棵树上

相当于判断两个点所在的树是否有同一个根。

完整代码

题目：洛谷 P3690 【模板】动态树（LCT），这题只需要单点修改，本质是一样的。

struct LinkCutTree {
	int fa[100005], son[100005][2], siz[100005], swp[100005];
	int val[100005], Xor[100005];

	void pushup(int now) {
		siz[now] = siz[son[now][0]] + siz[son[now][1]] + 1;
		Xor[now] = Xor[son[now][0]] ^ val[now] ^ Xor[son[now][1]];
		return ;
	}
	void pushdown(int now) {
		if(!swp[now]) return ;
		swap(son[now][0], son[now][1]);
		swp[son[now][0]] ^= 1, swp[son[now][1]] ^= 1;
		swp[now] = 0;
		return ;
	}
	int isRoot(int now) {return now != son[fa[now]][0] && now != son[fa[now]][1];}
	int get(int now) {return now == son[fa[now]][1];}
	void rotate(int x) {
		int y = fa[x], z = fa[fa[x]], chk = get(x);
		if (!isRoot(y)) son[z][get(y)] = x;
		son[y][chk] = son[x][chk ^ 1], fa[son[x][chk ^ 1]] = y;
		son[x][chk ^ 1] = y, fa[y] = x;
		fa[x] = z;
		pushup(y), pushup(x);
		return ;
	}
	void splay(int now) {
		vector<int> stk;
		stk.push_back(now);
		for (int i = now; !isRoot(i); i = fa[i]) stk.push_back(fa[i]);
		while (!stk.empty()) pushdown(stk.back()), stk.pop_back();
		for (int f; f = fa[now], !isRoot(now); rotate(now))
			if (!isRoot(f)) rotate(get(f) == get(now) ? f : now);
		return ;
	}
	void access(int now) {
		for (int lst = 0; now; lst = now, now = fa[now]) splay(now), son[now][1] = lst, pushup(now);
		return ;
	}
	void makeRoot(int now) {access(now); splay(now); swp[now] ^= 1; return ;}
	void link(int u, int v) {makeRoot(u); fa[u] = v; return ;}
	void cut(int u, int v) {makeRoot(u); access(v); splay(v); son[v][0] = fa[u] = 0; return ;}
	int find(int now) {
		access(now), splay(now);
		pushdown(now);
		while (son[now][0]) now = son[now][0], pushdown(now);
		splay(now);
		return now;
	}
	void split(int u, int v) {makeRoot(u); access(v); splay(u); return ;}
	void update(int u, int _val) {split(u, u); val[u] = Xor[u] = _val; return ;}
	int query(int u, int v) {split(u, v); return Xor[u];}
	int isConnected(int u, int v) {return find(u) == find(v);}
};

时间复杂度

每次操作均摊是 $O(\log n)$ 的，证明还不会。

分类

文章目录