LCT简单介绍
LCT复杂介绍

看不懂就认真听讲，这玩意真的很抽象

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node{
	int ch[2],fa,val,sum;
	int rev;
}tree[N];
int n,m;
void pushup(int x){
	tree[x].sum = tree[tree[x].ch[0]].sum^tree[x].val^tree[tree[x].ch[1]].sum;
}
void pushrev(int x){
	swap(tree[x].ch[0],tree[x].ch[1]);
	tree[x].rev^=1;
}
void pushdown(int x){
	if(tree[x].rev){
		pushrev(tree[x].ch[0]);
		pushrev(tree[x].ch[1]);
		tree[x].rev = 0;
	}
}
int Get(int x){
	return x == tree[tree[x].fa].ch[1];
}
int isroot(int x){
	return tree[tree[x].fa].ch[0]!=x && tree[tree[x].fa].ch[1]!=x;
}
void rotate(int x){
	int y = tree[x].fa,z=tree[y].fa,chk=Get(x);
	if(!isroot(y))tree[z].ch[y==tree[z].ch[1]] = x;tree[x].fa = z;
	tree[y].ch[chk] = tree[x].ch[chk^1];if(tree[x].ch[chk^1])tree[tree[x].ch[chk^1]].fa = y;
	tree[x].ch[chk^1] = y;tree[y].fa = x;
	pushup(y);
	pushup(x);
}
void update(int x){
	if(!isroot(x))update(tree[x].fa);
	pushdown(x);
}
void splay(int x){
	update(x);
	while(!isroot(x)){
		int y = tree[x].fa;
		if(!isroot(y)){
			if(Get(x)==Get(y))rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
}
void access(int x){
	for(int y=0;x;x=tree[x].fa){
		splay(x);
		tree[x].ch[1] = y;
		y = x;
		pushup(x);
	}
}
void makeroot(int x){
	access(x);
	splay(x);
	pushrev(x);
}
int findroot(int x){
	access(x);
	splay(x);
	while(tree[x].ch[0])pushdown(x),x=tree[x].ch[0];
	splay(x);
	return x;
}
void split(int x,int y){
	makeroot(x);
	splay(x);
	access(y);
}
void link(int x,int y){
	makeroot(x);
	splay(x);
	if(findroot(y)!=x){
		tree[x].fa = y;
	}
}
void cut(int x,int y){
	makeroot(x);
	splay(x);
	if(findroot(y)==x && tree[y].fa == x && tree[y].ch[0] == 0){
		tree[x].ch[1] = tree[y].fa = 0;
		pushup(x);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>tree[i].val;
	}
	for(int i=1;i<=m;i++){
		int pos,x,y,z;
		cin>>pos>>x>>y;
		if(pos==0){
			split(x,y);
			splay(y);
			cout<<tree[y].sum<<endl;
		}
		else if(pos==1){
			link(x,y);
		}
		else if(pos==2){
			cut(x,y);
		}
		else{
			splay(x);
			tree[x].val = y;
			pushup(x);
		}
	}
	return 0;
}