参考&&推荐：
一、概括
一种支持维护树的森林的算法。
采用实链剖分，多棵splay维护每个实链，键值就是节点的深度。
即，中序遍历就是这个链从上到下的节点组成。
同一个原树上的splay之间也连接，但是不同的实链的splay之间的父子边单向，由儿子指向父亲。
即，认父不认子。
也就是说，一个节点可以成为多个节点的父亲，但是最多只认一个左儿子，一个右儿子。
可以支持，
1.加入一条边（连接两棵树），
2.删除一条边
3.处理一条路径上的询问。
二、核心思想
1.实链剖分
区别于重链剖分和长链剖分，实链剖分的实链是动态的。
即，轻儿子重儿子随便换。根据需求会换不同的儿子。
2.原树和辅助树分开处理。
辅助树即splay（森林）
一棵原树可以认为是一棵部分联通的splay，也可以看做是多个splay，之间认父不认子
（以下称维护一条链的splay叫小splay，整个原树的splay叫大splay）
原树和辅助树没有区分开是初学者懵逼的一大原因。
splay的中序遍历就是这个链从上到下的节点组成。
可以参考上面第二篇博客。
3.每次提取一条完整的链进行处理。两端就是路径的起始终止节点。
“两端就是路径的起始终止节点。”这句话尤为关键。
makert之后access之后splay就可以把一个链放进一个子树里，轻松查找。（类似于普通splay区间查询）
还有一些性质，可以参考第一篇博客。
1.深度为键值，严格递增（显然，splay不可能存在两个点键值相同）
2.每个点属于一个小splay
3.认父不认子。最多一个重儿子
三、函数
1.access（灵魂函数）
access意为进入，接近。
就是打通一条root到x的路径。把root到x的路径变成实链。
无关的边都变成轻链。
摘自：LCT总结——概念篇+洛谷P3690[模板]Link Cut Tree(动态树)（LCT，Splay）
A是树根，access(N)
这里我们直接把轻边变成重边。
void access(int x){ for(int y=0;x;y=x,x=t[x].fa){ splay(x);t[x].ch[1]=y;pushup(x); } }
开始扔掉右儿子，就是扔掉N-O这块子树。
发现一个关键的性质，
这样，N和A在同一个小splay里面，N和A的路径上的点就是这个splay中的所有点。
2.splay（灵魂函数）&&rotate&&nrt
注意：这里splay仅在小splay中进行。都是把x转到这个小splay的根。
与一般splay不同的是，
LCT中splay的节点编号就是原树节点编号。可以随机访问。没有kth这一步
也就意味着，pushdown必须跟上。
用一个栈记录父亲，然后依次pushdown
之后像原来一样splay即可。
void splay(int x){ int y=x,z=0; sta[++z]=y; while(nrt(y)) y=t[y].fa,sta[++z]=y; while(z) pushdown(sta[z--]); while(nrt(x)){ y=t[x].fa,z=t[y].fa; if(nrt(y)){ rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x); } rotate(x); } pushup(x); }
值得注意的是，由于不能转出去，所以必须有一个nrt（not root）判断是否x是当前小splay的根。
通过father认不认这个x儿子判断是否为根。
否，返回1，是，返回0
bool nrt(int x){ return (t[t[x].fa].ch[0]==x)||(t[t[x].fa].ch[1]==x); }
由于认父不认子，所以小splay的根的father不能设置儿子关系。
void rotate(int x){ int y=t[x].fa,d=t[y].ch[1]==x; t[t[y].ch[d]=t[x].ch[!d]].fa=y; if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;//nrt注意 else t[x].fa=t[y].fa;//无论如何要设置x的fa t[t[x].ch[!d]=y].fa=x; pushup(y); }
3.makert&&reverse
由于深度单调递增，所以实链一定是竖直往下的。
对于x到y的路径，x,y可能不在一个实链上。
原树是一棵无根树，所以可以随时换根。
引入makert函数，把x钦定成为原树的根。
只要调整中序遍历即可。
access(x),splay(x)，然后reverse(x)，那么，就相当于直接翻转。
那么，本来x是和root相连的实链的底端，这样reverse一下，直接变成了根！！
神奇操作。
void rev(int x){ ls^=rs^=ls^=rs; t[x].r^=1; } void makert(int x){ access(x); splay(x); rev(x); }
4.findrt
查找一个点所在的原树的根。
找中序遍历第一个即可。
int findrt(int x){ access(x);splay(x); while(t[x].ch[0]) x=t[x].ch[0]; return x; }
值得注意的是，原树的根现在不是所属小splay的根了，根变成了x
5.split
提出x到y的路径。
根据access的得出的性质可以发现，makert(x),再access(y)，就把x到y的路径打通了。
然后splay(y),那么这个路径就是y和y的左子树。
void split(int x,int y){ makert(x);access(y);splay(y); }
之后可以直接查询y的信息。
6.link
连接原树中x到y
判断是否在同一个原树里。然后把x连向y一条认父亲边。
y先不认x这个儿子，必要的时候会access
void link(int x,int y){ makert(x); if(findrt(y)==x) return; t[x].fa=y; pushup(y); }
7.cut
判断是否相连 。
makert再findrt后，如果相连，y一定是x的father，x一定是y的左儿子。
如果x的father不是y，或者x有右儿子。则没有这条边。
否则断开。
void cut(int x,int y){ makert(x); if(findrt(y)!=x||t[x].fa!=y||t[x].ch[1]) return; t[x].fa=t[y].ch[0]=0; pushup(y); }
8.pushup
维护权值
void pushup(int x){if(x)t[x].s=t[rs].s^t[ls].s^t[x].v;}
9.pushdown
主要是下放reverse标记。
void pushdown(int x){ if(t[x].r){ t[x].r=0; rev(ls);rev(rs); } }
四、比较区别&&优势所在
1.与普通平衡树
见splay函数区别。
2.树链剖分、并查集比较
支持动态加边，删边，还可以支持维护链的信息。
五、应用
支持的操作就是基本应用。
留坑。
原文：https://www.cnblogs.com/Miracevin/p/9955164.html