LCT 小记
前言
在 OI 中，对于常规的树论问题，其树的形态一般是静态的。
但往往会存在一批毒瘤出题人，他们把树的形态变成了动态的，出现了 加边/删边 等操作。
而对于这类 「动态树问题」，我们有三种常见的数据结构可以维护，而本文将简单地引入其中的一种。
LCT。
以下简称这类处理动态树问题的数据结构为动态树，但请注意动态树的本意指的是这类问题而非这类数据结构。
为什么要用动态树
前面我们提到，动态树可以解决一些树的形态有变化的问题，最简单的一个例子莫过于动态加边删边的路径权值和。
这样的问题在静态时很容易用树链剖分等手段解决，而变为动态则不那么容易。
但其中某些问题也可以通过分治（线段树分治、时间分块、时间倒流……）一类方法解决，比如动态加边最小生成树。
但事实上，动态树除了解决这些动态的问题，还有别的好处。
- 时间复杂度更低
（虽然常数更大），树剖的大多数题目都是 \(\lg^2\) 起步的，因为需要另一个数据结构来维护。 - 可以将一些静态的问题做简单，典型的例子是换根类问题，思维难度会降低。
暂时想不到别的了。/kk
总之，动态树有着其特殊的作用。
关于三种动态树
我只写过 LCT，另外俩都是瞎看了之后猜的。
LCT 即 Link-Cut Tree，思路比较直接，你要动态树，那我直接动态地维护树链。
回顾重链剖分，本质只是保证了链的数量级，而链怎么取不影响正确性，于是我们可以考虑自己随意钦定树链，再分析其复杂度。
而由于我们需要动态的更改树链，线段树便不能胜任，于是可以采用平衡树进行。
显然对树链的操作包含 拼接、切断以及整体修改，故采取一些可以 维护区间 的平衡树，如：Splay，FHQ-Treap。
然后势能分析摊一下，用 Splay 摊进去变成 \(\lg n\)，而 FHQ-Treap 据别人分析是 \(\lg^2 n\) 的。
而这过程中对链的剖分，不受树的形态影响，我们于是称作 实链剖分，而相应的，重儿子/轻儿子 就变成了 实儿子/虚儿子。
这便是 LCT 的大体思想，不过细节上还有很多问题有待商榷。
ETT 即 Euler Tour Tree，顾名思义基于树的欧拉回路。
这玩意儿我不是很清楚，似乎思路是用数据结构维护这条 欧拉回路 的序列。
当然由于我们涉及到加删边，于是同样使用可以 维护区间 的平衡树，以对这个序列进行 拼接、切断、翻转 等操作。
理论上这个其实比 LCT 更简单（你只需要把修改之后的欧拉回路拼出来），但是它只适用于维护子树信息，而很难处理链。
我猜是因为欧拉回路上树链比较分散，不过似乎它仍然可以通过一些奇淫技巧跑部分树链信息。
但是后文将提到，LCT 同样可以维护一些子树信息，所以这家伙就被丢进 recycle 里了（大不了上面还顶着个 SATT）。
SATT 是 Top Tree 的一种 Self-Adjusting Top Tree 的简称，这个玩意儿的理论和前两位大相径庭。
它基于这么一个事实：对于任意一棵树，我们都可以运用 树收缩 理论来将它收缩为一条边。
树收缩理论的操作即 Compress 和 Rake，这两个分别针对 2度/1度 的点进行操作，把他们缩进其他点之间，形成 树簇（Cluster）。
Top Tree 所做的，就是在树簇上进行维护，然后反映树上的信息，具体的流程……完全不会，我只知道这个也用 Splay，并且是要三度化。
所以大家先去学 Splay Tree 吧！
瞎扯了这么多，其实只是想告诉各位，动态维护一棵树的方法是很多的。
这些方法不一定用来跑动态树，说不准哪天考试时就能给你一点启发呢？
好吧其实是我想水点字数。
关于 LCT
前文提到，LCT 的本质是树链剖分，通过随意钦定实链保证灵活性。
出于这个需要，固定结构的线段树不在适合我们，于是我们选择了平衡树。
而 Splay Tree 可以通过势能分析和 LCT 的复杂度摊在一起，故一般用它来写 LCT，当然你也可以 FHQ-Treap。
总之现在来考虑一个树的剖分。
可以发现，每条实链之间是相对独立的，于是我们把它丢进一棵 Splay Tree，使之中序遍历得到这条实链从上往下的点
同时为了表现 Splay Tree 之间的关系，我们把它的根的父亲，设为这条实链顶端的父亲（没有就是空），表示虚边。
在这里我们要强调一些事实，他们将帮助我们之后的理解：
Splay Tree 中左边的点深度严格小于右边的点。
对 Splay Tree 内部的操作（尤指旋转）不应影响虚边上的父亲，因为其中序遍历不被改变。
虚边永远在 Splay Tree 的根节点上，尽管不由根节点通过这条边和父亲连接（通过这条虚边的是 Splay Tree 最左端的点和父亲）。
然后我们就可以对这些实链进行操作，并影响原树了。
具体地说，我们有这些基础操作：
splay(p)，将 p 旋转为所在实链的 Splay Tree 上根节点。
access(p)，将 p 到原树的根这条路径串成实链，放进一棵 Splay Tree 里，并将 p 作为这棵 Splay Tree 的根。
make_root(p)，将 p 换为原树的根。
find_root(p)，找到 p 在原树上的根。
然后我们就能实现这样的操作：
split(p,q)，得到原树上 p 到 q 的路径。
link(p,q)，用一条边连接 p 和 q。
cut(p,q)，删掉 p 和 q 之间的边。
让我们逐个来看这些操作的实现。
LCT 的基础实现
在此之前做一些基础约定。
节点的定义为：
struct Node{
Node *ch[2],*fa;
Info info;
Tag tag;
};
其中 info 是自选的维护信息，tag 是一个至少包含是否有翻转操作的标记。
然后 pull 代表从儿子上传信息，push 则为下放标记，reverse 是翻转操作。
这些维护可暂时看作和 Splay Tree 中一样，但事实上是不同的。
splay(p)
这个函数来自 Splay Tree，故不做解释。
但需要注意旋转时判断父亲是否存在，不能根据父亲是否为 0 来判断，因为我们存在虚边。
使用这个函数来判断父亲是否为空。
void is_root(Node *p){
return p->fa==nullptr||(p->fa->ch[0]!=p&&p->fa->ch[1]!=p);
}
然后就和一般的 splay 操作没什么区别了。
access(p)
这里我们将 p 到根的路径串起来，考虑其步骤。
首先我们记 p 目前所在的实链顶端是 x，显然我们可以通过 splay 操作把 p 旋成根。
此时 p 的父节点 y 就代表原树上 x 的父亲，也表出了这条连接 x 和 y 分别所在两根实链的虚边。
那么我们只需要 p 到根的路径就行了，所以不难想到我们把 y 的右子树断开，然后改接到 p，并更新信息。
这样肯定是对的，因为中序遍历上到了 y 后就会到 x，这条边是正确的，而 y 之前与 x 之后的没有被改变。
接下来我们把这条大的实链做同样的操作，一路走到根就 OK 啦。
void access(Node *p){
for(Node *q=p,t=nullptr;q;t=q,q=q->fa)
splay(q),q->ch[1]=t,pull(q);
splay(p);
}