AgOH 大佬的视频：https://www.bilibili.com/video/BV1G4411z7mN
link-cut-tree 用来维护动态森林，可以支持连边、断边、查询树链信息的操作，树链剖分的加强版
实链剖分：每个非叶子节点都有一个实儿子，和它之间的边是实边，和其它儿子间的边都是虚边。实边和虚边是可以相互转化的
lct 中，使用单向边（从儿子到父亲）来表示虚边，双向边表示实边
lct 具体由 splay 来维护，满足这些性质：
access 操作，最基本的操作，将某一结点与它在原树中的根节点之间的路径打通成一条实链
对于当前的一个 \(x\)，先把它伸展到它所在的 splay 的根节点（注意区分原图和 splay），把这个 \(x\) 的右儿子修改为上一个 \(x\)（因为上一个的深度肯定比这个大，所以是右儿子）
修改后，\(x\) 和它原来的右儿子之间边变成了虚边
最后 \(x\) 变成它的父亲（经过一条虚边）
初始时 \(x\) 当然是 null
makeroot 操作：让一个节点变成他在原树中的根
很简单，就先把 \(x\) 用一个 access，然后再伸展到根
此时，由于 \(x\) 是深度最深的，所以它没有右儿子，然后如果把这棵树反转一下，那么中序遍历也就都反转了（像文艺平衡树那样），此时 \(x\) 深度最小，变成了根
反转当然就是用懒标记了
findroot 操作：找到一个节点在原树中的根
还是打通 \(x\) 到根的路径，然后把它伸展到 splay 的根
此时，因为根的深度在原树中最小，所以就从 splay 的根开始，一直往左儿子走，走到不能再走，最后那个点就是中序遍历的第一个点，深度最小，也就是原树的根了
link 操作：将两个点连边，要处理数据不合法的情况
先把其中一个点，\(x\) 弄成原树的根节点
如果 \(y\) 不在 \(x\) 的树中（用 findroot 来处理），就连一条虚边，\(x\) 的父指针指向 \(y\)
cut 操作：将两个点的边断开，同样要处理数据不合法的情况
还是把 \(x\) 先弄成原树的根节点
首先如果 \(y\) 不在这棵树，肯定不用断边。如果在这个 splay，当且仅当 \(x\) 和 \(y\) 在中序遍历中相邻时，他们之间才有边
也能简单的判断出来：如果 \(y\) 的父亲不是 \(x\)，显然不行
如果 \(y\) 有左儿子，也不行，它的左儿子会比 \(y\) 中序遍历靠前，而 \(x\) 的中序遍历肯定在最前（它被变成根了），所以叶不是相邻的
split 操作：把两个点之间的路径放到一个 splay 上摘出来，方便做一些处理
把 \(x\) 变成根，然后打通 \(y\) 和 \(x\) 之间的路径，再把 \(x\) 旋转到根，方便访问
然后查询操作用 split 完成，更改节点权值的的操作就把对应的点伸展到 splay 的根进行处理
还有记得下方标记，一些细节问题和一般的 splay 还是有区别的
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘) y=0;c=std::getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 100005
struct LCT{
struct tr{
tr *fa,*son[2];
int val,res;
int tag;
}*null,*pos[N],dizhi[N];
#define ident(tree,fa) (fa->son[1]==tree)
#define pushup(tree) tree->res=tree->son[0]->res^tree->son[1]->res^tree->val
#define notroot(tree) (tree->fa->son[0]==tree||tree->fa->son[1]==tree)
inline void connect(tr *tree,tr *fa,int k){fa->son[k]=tree;tree->fa=fa;}
inline void pushdown(tr *tree){
if(!tree->tag) return;
tree->son[0]->tag^=1;tree->son[1]->tag^=1;
std::swap(tree->son[0],tree->son[1]);
tree->tag=0;
}
inline void rotate(tr *tree){
tr *fa=tree->fa,*faa=fa->fa;
pushdown(fa);pushdown(tree);
int k=ident(tree,fa);
connect(tree->son[k^1],fa,k);
tree->fa=faa;
if(notroot(fa)) faa->son[ident(fa,faa)]=tree;//fa 是跟，fa faa 之间就是虚边
connect(fa,tree,k^1);//保证顺序，在此语句更改 fa->fa 之前，判断 notroot(fa)
pushup(fa);pushup(tree);
}
inline void splay(tr *tree){
reg tr *fa,*faa;
while(notroot(tree)){
fa=tree->fa;faa=fa->fa;
if(notroot(fa)) ident(fa,faa)^ident(tree,fa)?rotate(tree):rotate(fa);
rotate(tree);
}
}
inline void access(reg tr *x){
for(reg tr *lastx=null;x!=null;lastx=x,x=x->fa){
pushdown(x);
splay(x);
x->son[1]=lastx;pushup(x);
}
}
inline void makeroot(tr *x){
access(x);
splay(x);
x->tag^=1;
}
inline tr *findroot(tr *x){
access(x);splay(x);
while(x->son[0]!=null) pushdown(x),x=x->son[0];
splay(x);
return x;
}
inline void link(tr *x,tr *y){
makeroot(x);
if(findroot(y)!=x) x->fa=y;
}
inline void cut(tr *x,tr *y){
makeroot(x);
if(findroot(y)!=x||y->fa!=x||y->son[0]!=null) return;
y->fa=x->son[1]=null;
pushup(x);
}
inline void split(tr *x,tr *y){
makeroot(x);
access(y);splay(y);
//splay(y) 以后，y 没有右儿子，且其左儿子是一条通到 x 的实链
}
inline void creat(int i,int val){
pos[i]=&dizhi[i];
dizhi[i].res=dizhi[i].val=val;
dizhi[i].son[0]=dizhi[i].son[1]=dizhi[i].fa=null;
}
}lct;
int main(){
lct.null=&lct.dizhi[0];
int n=read(),m=read();
for(reg int i=1;i<=n;i++) lct.creat(i,read());
reg int op,x,y;
while(m--){
op=read();x=read();y=read();
if(!op) lct.split(lct.pos[x],lct.pos[y]),printf("%d\n",lct.pos[y]->res);
else if(op==1) lct.link(lct.pos[x],lct.pos[y]);
else if(op==2) lct.cut(lct.pos[x],lct.pos[y]);
else{
lct.splay(lct.pos[x]);
lct.pos[x]->val=y;
pushup(lct.pos[x]);
}
}
return 0;
}
原文：https://www.cnblogs.com/suxxsfe/p/13454347.html