动态树问题：维护一个森林，支持删除某条边，加入某条边并保证时刻是一个森林，我们需要维护森林的一些信息，一般的操作有询问两点连通性，询问两点路径的权值和，修改某点的权值。
基本介绍
$LCT$是用来解决动态树问题的数据结构，各种操作的时间复杂度都是$O(log\ n)$的（不太会证），我们对整个森林进行虚实链剖分，并保证原树中每个节点最多只有一个儿子是通过实链连接的，如图所示，就是满足条件的一种情况（此时森林有两棵树）。
然后我们用$splay$维护每条实链，并将这些$splay$称为辅助树（原树就是由虚实链构成的树），使$splay$的中序遍历就是该实链从最高点到最低点的路径。注意：
- 每棵$splay$维护一条实链，$splay$中的节点不会记录与其通过虚边连接的儿子。
- 辅助树的各棵$splay$之间并不是孤立的，每棵$splay$的根节点会记录其在另一棵辅助树中的父亲（每个树中只有一棵$splay$的父亲为$0$）
- 原树中某点的父亲不等于辅助树中某点的父亲
- 辅助树可以在满足条件的情况下换根
- 辅助树的根节点的父亲“不认”这个根节点
- 原树中每个节点最多只有一个通过实边连接的儿子，这样才能保证每棵$splay$维护的都是一条链
下面抛出例题，通过此例题来讲解$LCT$的各种操作：
维护的信息
struct node{
int s[2],p,v;//儿子、父亲、权值
int sum,rev;//异或和、翻转标记，虽然本题无翻转操作，但LCT的基本操作要用到
}tr[N];isroot
bool isroot(int u){//判断u是否是其所在splay的根
return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}splay的函数
我们需要对原本的部分$splay$函数进行小小的修改。
pushup
//本题维护异或和
void pushup(int u){
tr[u].sum=tr[tr[u].s[0]].sum^tr[tr[u].s[1]].sum^tr[u].sum;
}pushdown
//经典的翻转操作
void pushrev(int u){
swap(tr[u].s[0],tr[u].s[1]);
tr[u].rev^=1;
}
void pushdown(int u){
if (tr[u].rev){
pushrev(tr[u].s[0]);
pushrev(tr[u].s[1]);
tr[u].rev=0;
}
}rotate
void rotate(int x){
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
//唯一的不同处，辅助树根节点的父亲不能记录该根节点为儿子
if(!isroot(y)) tr[z].s[tr[z].s[1]==y]=x;
tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}splay
//LCT中我们只用到了把点旋转到根的操作，因此只有一个参数
void splay(int x){//把x旋转到所在splay的根
//我们要先把辅助树的根节点到该点路径上的懒标记下传
static int stk[N];
int tt=0,t=x;
stk[++tt]=t;
while(!isroot(t)) stk[++tt]=t=tr[t].p;
while(tt) pushdown(stk[tt--]);
while (!isroot(x)){
int y=tr[x].p,z=tr[y].p;
if(!isroot(y))
if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
else rotate(y);
rotate(x);
}
}access
//将x和其所在原树的根节点通过实边连起来，并把x旋转到辅助树的根
void access(int x){
int z=x;//记录初始的节点编号
//y初始为0，表示把x和它下面的点断开
for(int y=0;x;y=x,x=tr[x].p){//x沿着虚边往上跳
splay(x);//先转到当前辅助树的根
tr[x].s[1]=y,pushup(x);//把上个树接到中序遍历后面
}
splay(z);//把初始的节点转到根
}对于正确性，我们知道我们是从$x$节点往根跳，深度是递减的，因此$y$是$x$的右儿子，而我们也能时刻保证原树中每个节点只有一个实边儿子，因为我们把$x$旋转到辅助树的根后，它的儿子深度比它大，因此一定是$x$的右儿子，然后我们把$x$的右儿子修改为$y$，保证了每个点只有一个实边儿子。
makeroot
void makeroot(int x){//将x变为原树的根
access(x);//此时x为辅助树的根节点，且右儿子为0
pushrev(x);//翻转左右子树，此时x左儿子为0，因此x是深度最低的点，x是原树根节点
}findroot
int findroot(int x){//找到x所在的原树的根节点,再将原树的根节点旋转到辅助树的根节点,此时根节点无左儿子
access(x);//打通根节点到x的实链,当前x位于辅助树的根节点位置
while(tr[x].s[0]) pushdown(x),x=tr[x].s[0];//找到辅助树中序遍历的第一个元素
splay(x);//转到根节点
return x;
}split
void split(int x,int y){//将x到y的路径变为实边路径,并把y变为辅助树的根
makeroot(x);//先把x设为原树的根
access(y);//在打通根到y的实链，此时y是辅助树的根，y的sum就是x~y路径上的权值异或和
}link
void link(int x,int y){//若x,y不连通,则加入(x,y)这条边
makeroot(x);//先把x设为根
if(findroot(y)!=x) tr[x].p=y;//如果不连通,在x、y间添加一条虚边,因为我们维护的是森林
}cut
void cut(int x,int y){//若边x,y存在,则删掉x,y这条边
makeroot(x);//把x变为原树的根，则此时y一定是x的右儿子
//因为x,y可能并不通过实边连接，此时我们findroot(y)便能使其连通，同时x会被转到辅助树的根节点
if(findroot(y)==x&&tr[x].s[1]==y&&!tr[y].s[0]){//保证辅助树中y是x的后继节点
tr[y].p=tr[x].s[1]=0;
pushup(x);
}
}这样，我们就讲完了$LCT$的基本操作，然后放上完整$AC$代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
#define ls tr[u].s[0]
#define rs tr[u].s[1]
struct node{
int s[2],p,v;
int sum,rev;
}tr[N];
bool isroot(int u){
return tr[tr[u].p].s[0]!=u&&tr[tr[u].p].s[1]!=u;
}
void pushup(int u){
tr[u].sum=tr[ls].sum^tr[u].v^tr[rs].sum;
}
void pushrev(int u){
swap(tr[u].s[0],tr[u].s[1]);
tr[u].rev^=1;
}
void pushdown(int u){
if (tr[u].rev){
pushrev(tr[u].s[0]);
pushrev(tr[u].s[1]);
tr[u].rev=0;
}
}
void rotate(int x){
int y=tr[x].p,z=tr[y].p;
int k=tr[y].s[1]==x;
if(!isroot(y)) tr[z].s[tr[z].s[1]==y]=x;
tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[x].s[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void splay(int x){
static int stk[N];
int tt=0,t=x;
stk[++tt]=t;
while(!isroot(t)) stk[++tt]=t=tr[t].p;
while(tt) pushdown(stk[tt--]);
while (!isroot(x)){
int y=tr[x].p,z=tr[y].p;
if(!isroot(y))
if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
else rotate(y);
rotate(x);
}
}
void access(int x){
int z=x;
for(int y=0;x;y=x,x=tr[x].p){
splay(x);
tr[x].s[1]=y,pushup(x);
}
splay(z);
}
void makeroot(int x){
access(x);
pushrev(x);
}
int findroot(int x){
access(x);
while(tr[x].s[0]) pushdown(x),x=tr[x].s[0];
splay(x);
return x;
}
void split(int x,int y){
makeroot(x);
access(y);
}
void link(int x,int y){
makeroot(x);
if(findroot(y)!=x) tr[x].p=y;
}
void cut(int x,int y){
makeroot(x);
if(findroot(y)==x&&tr[x].s[1]==y&&!tr[y].s[0]){
tr[y].p=tr[x].s[1]=0;
pushup(x);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>tr[i].v;
while(m--){
int type,x,y;
cin>>type>>x>>y;
if(type==0){
split(x,y);
printf("%d\n",tr[y].sum);
}
else if(type==1){
link(x,y);
}
else if(type==2){
cut(x,y);
}
else{//修改的话，我们先把x转到根，然后单点修改并pushup即可
splay(x);
tr[x].v=y;
pushup(x);
}
}
return 0;
}
