从例题开始：
P3690 【模板】动态树（LCT）
对于一棵静态的树，常见方法是树剖然后走链，但是在动态的情况下常见的重链或长链就会很慢，因为修改连边情况后就不满足性质了
引入一个新的方法：实链剖分，对于一个节点，任选一个儿子，连边为实边，其余为虚边，注意这里的实边是可以变化的
但是显然这样剖分的形式就不固定了，所以之前线段树维护的方法就不成立了，但是可以用 splay 解决
此时树变成了若干条实边和虚边，连接在一起的实边成为实链
对每条实链进行维护，使得 splay 的中序遍历为原树上深度从小到大排序的结果
对于虚边，作用是把这些 splay 连起来，方式如下：
-
找到该 splay 深度最小的节点，记为 k，若为根则不管
-
找到它的 fa，由它向当前 splay 的根连边
因为一个节点会有多个儿子，但是它只会存一个，就是认父不认子
区别于普通 splay，因为实链之间不能相互影响，操作时还需要判断是否为当前 splay 的根，如果是，返回-1，rotate 和 splay 函数区别不大
access：就是把点 x 到根路径上的点全部变成实边
首先将 x 转到当前 splay 的根，然后将 x 与 fa 之间的边变成实边，就是放到右儿子，然后处理 fa 所在子树，重复此操作直到整棵树的根
同时因为将 x 到根打包成一个 splay，所以 x 原来的实儿子变成虚儿子
makeroot：将 x 节点设为所在联通快的根
首先打通 x 到根的路径，此时 x 一定在这个子树的中序遍历的最后一位
如果我们将它设为根，那么它就是深度最小的点，但是他的 fa 作为深度第二大的点，理应在倒数第二位，翻转后会在第二位，这部分可以打懒标记实现
所以最后就是打通 x 到根的路径，然后把 x 转到根，给 x 打标记
同时将 x 转到根时，路径上的标记要全部下放
split：就是把 x 到 y 的路径变成实链，然后分成新的 splay，操作上就是先把 x 换到整棵树的根，然后打通 y 到根的路径，最后将 y splay 到子树的根
findroot：就是找到 x 所在点的实链的根，可以先将 x 转到根，此时因为根深度最小，暴力往左边找，注意下放标记，最后要转回去
link：连边，将 x 换到根，然后判断 y 和 x 是否在同一个联通快，不在就连一条虚边
cut：断边，先判断是否在一个联通快内，然后将路径独立出来，此时 y 若与 x 相连，则 y 在 x 的父亲且中序遍历上相邻，所以 x 不能有右子树
安装mysql 8.0.41)
安装mysql5.7.42)
)
（取上一条）和 LEAD()（取下一条）函数)
