动态树问题的引入
静态树问题
静态树问题的一般形式如下：
给定一个树，点和边可能有权。
要对这个树按时间顺序进行一些操作和询问。
操作可以修改点和边的权值。
询问可以对链和子树进行询问。
通俗的讲，所有在整个过程中树的结构不变的树论问题就叫静态树问题。
动态树问题
动态树问题是与静态树问题相对的，也就是说动态树问题可以改变树的结构。
其一般形式如下：
给定一个树，点和边可能有权。
要对这个树按时间顺序进行一些操作和询问。
操作可以修改点和边的权值或者修改树的结构。
询问可以对链和子树进行询问。
实链剖分的引入
我们先只考虑对链的询问，子树询问之后再进行解释。
静态树问题的经典处理思路是把树进行剖分，然后把每条树链当成一个序列，用线段树进行维护。
这样一个对链的询问就相当于是对若干个序列（树链）的区间进行询问。
但是对于动态树问题，因为树的结构会改变，因此简单的树链剖分就无法保证两点链上树链的数量级了。
因此我们考虑使用一种能够在树的结构改变时进行调整的树链剖分，从而解决动态树问题。
在 LCT 算法中，我们称这种剖分为实链剖分。
LCT 算法的大致思想
我们考虑用类似重链剖分的方法定义实链剖分。
令 \(rson(u)\) 为 \(u\) 实儿子，注意这个值可能不存在，且该值是可能随时变化的。
令形如 \((u,rson(u))\) 的边为实边，其他边为虚边。
令实边形成的链为实链，类似于重链，它有一些性质：
- 一条实链是一条深度严格递增的树链。
- 所有实链恰好剖分了整棵树，即每个结点恰好在一条实链上。
- 实链之间由虚边连接，且每条虚边中深度较大的点必然是一条实链的根。
- 任意一条连接两点的树链都可以被表示为若干条实链的上的区间连接而成的链。
- 与重链剖分不同，实链剖分出来的每条链不一定以叶子结点结尾。
由于在调整实链的过程中，可能涉及拆分链或合并链的操作，这用线段树不太方便维护，因此我们考虑采用适应性更强的平衡树（一般采用 splay 树）来维护。
具体来说，我们对每条实链用一个平衡树来维护。
即将该树链中的结点以深度为键，全部插入到一棵平衡树中。
由于我们要进行虚实边转换的操作，因此我们还要在平衡树森林中维护虚边，怎么表示虚边呢？
考虑对于一条虚边 \((u,v)\)（假设 \(dep_u >dep_v\)）。
发现 \(u\) 必然是其所在实链中深度最小的点，因此我们记不记录 \(u\) 其实不重要，只要知道它在哪条实链中即可。
因此我们从 \(u\) 所在平衡树的根向 \(v\) 在平衡树中的结点建一条边即可。
也就是将每个平衡树的根的父亲设为这条树链的深度最小的点在原树上由虚边连接的父亲（没有就不设）。
不难发现，这些平衡树与转化后的虚边形成了一棵新的树，与原树相对，我们称其为辅助树。
显然辅助树拥有比原树更加优秀的结构，因此在 LCT 算法中，我们通过维护辅助树来间接维护原树，通过将原树上的询问转化为辅助树上的询问来进行回答。
有一个小细节，就是如何在辅助树上区分实边和虚边。
发现如果一个点到其辅助树上父亲的边是虚边，那它的父亲是不会记录它这个儿子。否则其一定是父亲左右儿子中的一个。因此简单地判一下就行了。
同时我们发现想要把 \(x \to y\) 的一条边由实边转为虚边只要在 \(x\) 的儿子中去掉 \(y\) 即可。
由虚边转为实边也只要在 \(x\) 的儿子中加入 \(y\) 即可。（注意 \(y\) 可能会与 \(x\) 原有的儿子形成冲突，在后文中会有解释）
补充：Splay 树
splay 树本身是一个功能非常强大的平衡树，在 LCT 中应用的 splay 树其实只是它的一个阉割版，在此补充一下。
splay 树是一个基于旋转的平衡树，它有两种旋转操作：
- 对 \(x\) 单旋：将连接 \(x\) 与 \(fa_x\) 的边进行旋转，注意有左旋和右旋的区别。
- 对 \(x\) 双旋：先执行 \(zig(fa_x)\)，再执行 \(zig(x)\)。
splay 树的核心操作是 \(splay(x)\)，具体为将 \(x\) 旋转至根。
怎么旋转至根呢？当然是用上面的两种旋转操作。
具体为不断重复以下操作（下文中的 \(get(x)\) 表示 \(x\) 是其父亲的哪个儿子）：
- 如果 \(fa_x=root\)，对 \(x\) 单旋。
- 如果 \(get(fa_x)\not=get(x)\)，对 \(x\) 做两次单旋。
- 如果 \(get(fa_x)=get(x)\)，对 \(x\) 双旋。
可以证明，对一个 spaly 树执行 \(m\) 次任意位置 \(splay\) 操作的时间复杂度为 \(\Theta(n\log n+m\log n)\)。
因此，对 splay 树做任何一个简单操作，假设为 \(opt(x)\)。
具体为一个复杂度为 \(\Theta(dep_x)\)，且不会改变树的结构的操作。
我们都可以通过执行一次 \(spaly(x)\)，是的 \(opt(x)\) 的均摊时间复杂度变为 \(\Theta(\log n)\)。
LCT 算法的各种操作
Access(x)
这是 LCT 最重要的操作，作用是通过虚实边的切换使得 \(x\) 的到根链成为一条实链。
具体流程如下：
-
首先将 \(x\) 所在实链在 \(x\) 处断开，使得 \(x\) 是其所在实链的结尾结点。
具体实现方法是先执行 \(splay(x)\)，然后找到实链中 \(x\) 的儿子，假设为 \(y\)。
然后将 \(x\to y\) 的边变为虚边，也就是直接在 \(x\) 的儿子中去掉 \(y\)。
-
然后不断执行以下操作，使得 \(x\) 所在实链不断向根扩展，直到其包含根。
具体为：
（注意此时 \(x\) 已经是其所在 splay 的根）
先将 \(x\) 虚边连接的父亲 \(fa_x\) 也旋转到其 splay 的根，即执行 \(splay(fa_x)\)。
然后将 \(fa_x\) 所在实链中深度大于 \(fa_x\) 的点去掉，也就是将 \(fa_x\) 到其实链上儿子的边变为虚边，也就是将 \(fa_x\) 的右儿子断掉。
然后将 \(x\) 所在实链接到 \(fa_x\) 所在实链上，也就是将 \(fa_x\to x\) 的边变为实边，也就是将 \(x\) 设为 \(fa_x\) 的右儿子，注意这里是不会有冲突的。
这样就完成了一次扩展。
如果 \(fa_x\) 已经是根了，那操作就做完了，最后函数返回当前平衡树的根，也就是 \(fa_x\)。
否则，把 \(x\) 设为 \(fa_x\)，重复执行该操作。
注意到 \(Access(x)\) 操作的有返回值，是最后一次拓展的虚边的父亲，因此求 \(x\) 和 \(y\) 的 lca 的经典方法是：
- 先 \(Access(x)\)。
- 然后 \(Access(y)\)，其返回值就是 \(lca(x,y)\)。