【学习笔记】动态树 Link-Cut Tree

- 闲话

LCT 优秀博客：

• FlashHu 大佬的 cnblogs：https://www.cnblogs.com/flashhu/p/8324551.html

- 动态树 Link-Cut Tree

- 前置知识

• 「必学」Splay。
• 「重要」树链剖分 / 重链剖分（虽然并不需要用到，但是了解重链剖分的思想还是有用的）。
• 「必学」实链剖分。

实链剖分是一种动态的剖分方式。

对于一个点连向它儿子的所有边，我们选择一条边进行剖分。
被选择的边称为实边，其他边为虚边。
实边连接的儿子称为实儿子。
对于一条实边连接成的链，称为实链。

实链剖分的剖分结果是可变的，可以灵活调整。

和重链剖分的区别就是，重链剖分需要找到儿子子树大小最大的一个连重边，而实链剖分不需要。

何为 Link-Cut Tree

给定一棵树，有以下操作：

• 修改 \(x\) 的点权。
• 求出 \(x,y\) 的简单路径的点权和。
• 修改 \(x\) 子树每一点的点权。
• 求出 \(x\) 子树的点权和。

一个很简单的「树链剖分」题目，不是吗？

如果我们增加几个操作呢？

• 断开 \(x \to y\) 这一条边。
• 连上 \(x \to y\) 这一条边。
• 把这棵树改成以 \(x\) 为根。

很显然，因为这棵树要动态删边和加边，且有换根操作，维护静态树的树链剖分就无法处理这类题目了，「动态树 Link-Cut Tree，LCT」应运而生。

具体的，LCT 可以维护以下操作（引自 FlashHu cnblogs）：

• 查询、修改链上的信息（最值，总和等）
• 随意指定原树的根（即换根）
• 动态连边、删边
• 合并两棵树、分离一棵树
• 动态维护连通性
• 更多意想不到的操作

因为 LCT 是动态的数据结构，所以线段树等已不适合维护，引入「Splay」这种平衡树来维护之 \(^{\texttt{[1]}}\)。

LCT 实质上维护了一个 Splay 森林，有如下性质：

1. 每棵 Splay 都维护一条 原树的路径，这条路径满足节点深度依次增大，且中序遍历 Splay 得到的每个点的深度序列 严格递增。单独的一个点也可以是一棵 Splay。

   • 举个例子，这棵树的构造为 1(2,3)，即 \(1\) 号节点为树根，深度为 \(1\)，\(2,3\) 号节点分别为它的左右儿子，深度为 \(2\)。那么这个 Splay 森林可以是这样的：
   1. \(\texttt{[1,2][3]}\)，第一棵 Splay 维护 \(1 \to 2\) 这条路径，深度单调递增（\(1,2\)），第二棵维护 \(3\)，单独的一个点。
   2. \(\texttt{[1,3][2]}\)，第一棵 Splay 维护 \(1 \to 3\) 这条路径，深度单调递增（\(1,2\)），第二棵维护 \(2\)，单独的一个点。
   3. \(\texttt{[1][2][3]}\)，三个点都为一棵独立的 Splay。

   注意 \(\texttt{[1,2,3]}\) 这棵 Splay 是不合法的，因为 \(2,3\) 的深度相等。

2. 每个节点被包含且仅被包含在 一棵 Splay 内。

3. 由以上两条性质我们可以得出，每个节点只能和它的儿子连 一条实边，其余的儿子都和他连 虚边，并且每一条虚边的儿子所在的 Splay 要指向这个节点。但是这个节点并不能指向其儿子的 Splay（即 FlashHu 博客中的 认父不认子）。

- 具体操作

- \(\text{access}(x)\)

• LCT 最核心的操作。

• 打通根节点和指定节点的路径，即把根节点和 \(x\) 中间的路径都变成 实边，形成一条以根节点开始，指定节点结束的 Splay。

来几张图 \(^{\texttt{[2]}}\)：

假设一开始实边和虚边是这么划分的：

那么所形成的 Splay 森林 可能 是这样的（绿框中为一个 Splay）：

现在我们要 \(\text{access(N)}\)，把 \(\text{A} \to \text{N}\) 的路径都打通成实边，变成一颗 Splay。

根据性质 3，原来有些实边要变虚（因为 \(\text{A} \to \text{N}\) 的有些虚边要变实，同层只能有一条实边连向父亲）。那么原树可能要变成这样：

我们一步一步自底向上拉。

首先 \(\text{splay(N)}\)，把 \(\text{N}\) 转到所在 Splay 的根。

因为要 以指定节点结束，所以比他深且在一颗 Splay 中的点要去除。

因为性质 1，中序遍历 Splay 得到的每个点的深度序列 严格递增，所以我们把 \(\text{N}\) 右边的点去掉即可。即把 \(\text{N} \to \text{O}\) 这条边变虚。直接把 \(\text{N}\) 的右子树变空，然后让 \(\text{O}\) 所在 Splay 指向 \(\text{N}\) 即可。

如下图：

接下来要打通 \(\text{I} \to \text{L}\) 的边，首先找到 \(\text{N}\) 所在 Splay 指向的节点 \(\text{I}\)，并 \(\text{splay(I)}\)，让 \(\text{I}\) 转到其所在 Splay 的树根，这样保证它的右儿子肯定是它在原树中连的虚边（性质 1），把它的右子树置空。

然后就可以连接 \(\text{I} \to \text{L}\) 了，因为 \(\text{L}\) 所指向的点是 \(\text{I}\)，把 \(\text{L}\) 直接连到 \(\text{I}\) 的右子树即可。

- Reference

\(\texttt{[1]}\)：因为 LCT 的 makeroot 等操作需要翻转一棵树，使得 Treap、FHQ Treap 等平衡树均已不适用。

\(\texttt{[2]}\)：引自 https://www.cnblogs.com/flashhu/p/8324551.html