LCT就是动态树的一种，但是相比Top_Tree来说，处理子树能力不足（但是简单）。

LCT利用轻重路径的划分，也就是实边和虚边来实现边的删除和合并。

现在来说说LCT的几个重要操作：（默认会splay）

  • access(x) : 让x连到根上面，也就是让根到x的边全部变为实边。所以我们每次让当前节点splay到根，改变儿子，向上pushup传递信息即可。
  • makeroot(x) : 让x为根，也就是换根操作，我们先access(x)，之后x肯定为深度最大的点，然后splay到根即可。
  • find(x) : 找到原树的根，也是一样，我们先access(x) ，之后把根换到最底层，也就是把x，splay到顶点，然后一直向左儿子走即可走到原根。
  • split(x,y) ：向然x为根，即makeroot(x)，之后打通y到x的路径，access(y)，然后把y，splay到根即可得到以y为根，x到y的路径。
  • link(x,y) ：连接x，y两个点（变成实边），我们令x为根，如果y的根不为x就让x的父亲为y即可。
  • cut(x,y) ：切断x，y两点之间的边，先让x为根，如果满足y的父亲，y的根都为x且y没有左儿子，切断即可。

例题：Link_Cut_Tree例题

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int n,m,a[N];
struct Link_Cut_Tree{
	int cnt,st[N];
	struct node{int ch[2],fa,val,re;}t[N];
	inline void push_up(int p){
		t[p].val=t[t[p].ch[0]].val^t[t[p].ch[1]].val^a[p];
	}
	inline void push_re(int p){swap(t[p].ch[0],t[p].ch[1]); t[p].re^=1;}
	inline void push_down(int p){
		if(t[p].re){
			if(t[p].ch[0])	push_re(t[p].ch[0]);
			if(t[p].ch[1])	push_re(t[p].ch[1]); t[p].re^=1;
		}
	}
	inline bool isroot(int x){return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;}
	inline void rotate(int x){
		int y=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x,w=t[x].ch[!k];
		if(!isroot(y))	t[z].ch[t[z].ch[1]==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
		if(w)	t[w].fa=y; t[y].fa=x; t[x].fa=z;	push_up(y);
	}
	inline void splay(int x){
		cnt=1;	st[cnt]=x; int y=x;
		while(!isroot(y))	st[++cnt]=y=t[y].fa;
		while(cnt)	push_down(st[cnt--]);
		while(!isroot(x)){
			int y=t[x].fa,z=t[y].fa;
			if(!isroot(y))	rotate((t[y].ch[0]==x)^(t[z].ch[0]==y)?x:y);	rotate(x);
		}push_up(x);
	}
	inline void access(int x){
		for(int y=0;x;x=t[y=x].fa) splay(x),t[x].ch[1]=y,push_up(x); 
	}
	inline void makeroot(int x){access(x); splay(x); push_re(x);}
	inline int find(int x){
		access(x); splay(x); while(t[x].ch[0]) push_down(x),x=t[x].ch[0]; 
		splay(x);	return x;
	}
	inline void split(int x,int y){makeroot(x); access(y); splay(y);}
	inline void link(int x,int y){makeroot(x); if(find(y)!=x)	t[x].fa=y;}
	inline void cut(int x,int y){
		makeroot(x); 
		if(find(y)==x&&t[y].fa==x&&!t[y].ch[0]) t[y].fa=t[x].ch[1]=0,push_up(x);
	}
}tr;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	while(m--){
		int op,x,y;	scanf("%d %d %d",&op,&x,&y);
		if(op==0)	tr.split(x,y),printf("%d\n",tr.t[y].val);
		else if(op==1)	tr.link(x,y);
		else if(op==2)	tr.cut(x,y);
		else	tr.splay(x),a[x]=y; 
	} 
	return 0;
}