Link Cut Tree

一种对树进行动态加删边的数据结构。

实链剖分

与重链剖分最大的区别在于实链剖分可以随意选择一条连向儿子的边剖分，该边称为实边，其余称为虚边，对应的儿子称为实儿子。 一条由实边组成的链称为实链。

辅助树

一些 Splay 构成一个辅助树，维护原树。

1. 每颗 Splay 维护原树的一条路径，且中序遍历（左根右） Splay 得到原树自上而下的该路径。
2. 每颗 Splay 的根节点的父节点指向原树中这条链的父节点，是一条特殊的边，对应原树的一条虚边。
3. 由于辅助树的性质，我们只需要维护辅助树即可。

前置函数

写这篇博客之前我还不会 Splay ，故选择把相关函数当成黑盒使用。

1. Get(x) : \(x\) 是左儿子还是右儿子。
2. Splay(x) : 把 \(x\) 旋转到当前 Splay 的根。
3. Rotate(x) : 把 \(x\) 向上旋转一层。

常见操作

1. access(x) 把从根到 \(x\) 的所有点放在一条实链里，这是核心操作。

   int Access(int x) {
       int p;
       for (p = 0; x; p = x, x = f[x]) {
           Splay(x), ch[x][1] = p, PushUp(x);
       }
       return p;
   }