1 概述
首先我们需要知道一类问题，在这类问题中我们需要维护一个森林，支持加边和删边操作，然后要求维护树上的一些信息。这类问题称为动态树问题。
而 LCT，即 Link-Cut Tree，就是用于解决动态树问题的一种数据结构。
学习 LCT 之前需要对 Splay 这种平衡树有一定了解，当然两者在细节上还有一些差别。
2 实链剖分
我们先来看看如果不要求动态加边删边怎样做。假如给出一道这样的问题：
- 修改一个点的点权。
- 查询路径 \(x\to y\) 上点的点权异或和。
显然这个问题可以轻松用树链剖分解决掉。接下来我们加入加边删边操作之后普通的树链剖分就难以维护了，原因就在于树结构改变的同时树链剖分出来的重链也会改变。
考虑树剖维护链上操作的本质，我们其实就是给同一条重链上的点赋上连续的 \(\text{dfn}\) 编号，并且保证每个点到根节点经过的重链数量是 \(O(\log n)\) 级别的，然后再利用其他数据结构维护。
在动态树问题中，我们困难的地方就是对树时刻维护这样的链，上面已经说过树剖难以维护，所以我们更希望这个重链是由我们自行决定的。换句话讲，我们希望对每个节点自行指定重儿子和轻儿子然后进行维护。
这种划分方式就被称为实链剖分，而我们自行指定的儿子叫做实儿子和虚儿子（需要注意的是一个点不一定必须有实儿子）。然后整棵树就可以被划分成若干实链，接下来我们就需要利用 Splay 去维护每一条链。
然后我们就需要考虑怎样去维护这些链，我们还需要引入另一个东西。
3 辅助树
辅助树实际上就是维护每条链的 Splay 之间通过某种方式相连形成的树结构。可以理解为 Splay 维护的是每一条实链，而辅助树维护的就是一棵树；将一些辅助树放在一起就构成了 LCT，用于维护整个森林。
现在我们来看辅助树的性质：
- 辅助树有多个 Splay 组成，每个 Splay 维护原树的一条实链，且 Splay 的中序遍历对应实链从上到下的点。
- 辅助树上的 Splay 通过如下方式连成一棵树：对于一棵 Splay，其根节点的父亲指向其对应维护的实链的链顶的父亲。同时对于我们指向的这个点，我们仍然让它在辅助树上的儿子为空，以此表示这条边是虚边。也就是说，所有的虚边都是认父不认子的。
- 原树上的操作均可以转化为在辅助树上操作，所以接下来我们只需要考虑在辅助树上的操作即可。
举个例子，对于如下所示的原树：
其辅助树结构可能如下（显然这个结构会随 Splay 形态变化）：
然后我们来看一下原树和辅助树的关系：
- 原树的实链都在辅助树的同一个 Splay 中。
- 原树的虚边由儿子所在 Splay 的根节点指向父亲，但是这个点不指向根节点。
- Splay 上最多有两个实儿子，但是可能会有很多虚儿子。
- 原树的根不等于辅助树的根；原树上的父亲指向不等于辅助树上的父亲指向。
接下来就可开始实现 LCT 的基本操作了。