单独开一个。
基础原理
动态树上问题的新优选。通过划分类似重剖的虚实边，将原树变为若干 Splay 来维护，其大概支持的操作有：
-
加边删边
-
维护链信息
-
随意换根
-
维护连通性
-
维护可删除的子树信息
-
？
因为比较懒，所以简单写一点东西，以后有兴趣了可能会补一点吧。
LCT 维护的 Splay 有几个性质：
-
一个 Splay 内维护的为原树的一条链，其中序遍历与原链按深度小到大排序相同。
-
认父不认子，即父亲记录，虚儿子不记录，只记录实儿子。
接下来是几个操作，原本 Splay 的 \(\text{splay}\) 和 \(\text{notroot}\) 操作不再赘述，两个的作用分别为将当前点旋转到当前 Splay 的根上和判断当前点是否为根：
\(\text{access(x)}\)
将当前点到根的链打通，即全部变为实边，大概顺序为父亲先跳到 splay 根上，将右儿子设为当前点（为保证深度性质），然后更新信息，记得将原本的边全部清空。
inline void ac(ll x){for(ll y=0;x;x=fa[y=x]) sp(x),rs=y,ps(x);}
\(\text{makeroot(x)}\)
将当前点变为根，只需要先 \(\text{access}\)，然后将当前点转到 splay 根部，因为比当前点深度大的点在 \(\text{access}\) 断掉了，所以此时当前点只有左儿子，交换一下左右子树就能变成根。
inline void mr(ll x){ac(x),sp(x),rev(x);}
\(\text{split(x,y)}\)
把 \(x\) 到 \(y\) 这条链拿出来，没什么好说的了，先令 \(x\) 为根，将 \(x,y\) 路径打通，注意 \(\text{access(y)}\) 可能会将 \(x\) 转下去，所以要再将 \(x\) 或 \(y\) 转到根上。
inline void sp(ll x,ll y){mr(x),ac(y),sp(x);}
\(\text{findroot(x)}\)
注意不能 \(\text{makeroot}\)，直接 \(\text{access}\) 后 \(\text{splay}\) 就可以了，然后根一定在最左，直接下去找就好了，注意下放标记和结尾保证复杂度的 \(\text{splay}\)。
inline ll fr(ll x){ac(x),sp(x);while(ls) x=ls,pd(x);sp(x);return x;}
\(\text{link(x,y)}\)
直接令 \(x\) 为根，判断 \(y\) 与 \(x\) 根是否相同，不相同令 \(x\) 为 \(y\) 即可，相当于连了一条虚边。
inline void lk(ll x,ll y){mr(x);if(fr(y)!=x) fa[x]=y;}
\(\text{cut(x,y)}\)
还是令 \(x\) 为根，判断 \(y\) 与 \(x\) 没有点了，即 \(y\) 的左子树为空，然后将所有信息删掉，注意信息更新。
inline void ct(ll x,ll y){mr(x);if(fr(y)==x&&fa[y]==x&&!s[y][0]) fa[y]=s[x][1]=0,ps(x);}