P3690 【模板】动态树（Link Cut Tree）

刚学完分散的各个函数，不知道怎么用awa

#include<bits/stdc++.h>
using namespace std;
#define num 100010
int n,m,ch[num][2],fath[num],tag[num],size[num],w[num];
void pushup(int x){
	size[x]=size[ch[x][0]]^size[ch[x][1]]^w[x];
}
void pusher(int p){
	swap(ch[p][0],ch[p][1]);
	tag[p]=0;
}
void pushdown(int p){
	if(tag[p]){
		if(ch[p][0])pusher(ch[p][0]);
		if(ch[p][1])pusher(ch[p][1]);
		tag[p]=0;
	}
}
bool get(int x){
	return x==ch[fath[x]][1];
}
bool isroot(int x){
	return x!=ch[fath[x]][0]&&x!=ch[fath[x]][1];
}
void update(int p){
	if(!isroot(p))update(fath[p]);
	pushdown(p);
}
void rodate(int x){
	int y=fath[x],z=fath[y],k=get(x);
	if(!isroot(y))ch[z][ch[z][1]==y]=x;
	ch[y][k]=ch[x][!k],fath[ch[x][!k]]=y;
	ch[x][!k]=y;fath[y]=x;fath[x]=z;
	pushup(x);pushup(y);
}
int st[num],z;//栈，splay里从上到下pushdown 
void splay(int x){
	update(x);
	int y=x;st[++z]=y;
	while(isroot(y))st[++z]=y=fath[y];//向上入栈
	while(z)pushdown(st[--z]);//从上往下入栈 
	for(int fa;fa=fath[x],!isroot(x);rodate(x))
		if(!isroot(fa))
			rodate(get(fa)==get(x)?fa:x);
}
int access(int x){
	int p;
	for(p=0;x;p=x,x=fath[x]){
		splay(x);
		ch[x][1]=p;
		pushup(x);//更新 
	}
	return p;
}
void makeroot(int p){
	p=access(p);
	pusher(p);
}
void link(int x,int y){
	makeroot(x);
	splay(x);
	fath[x]=y;
}
void split(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
}
void cut(int x,int y){
	split(x,y);
	ch[y][ch[y][1]==x]=fath[x]=0;
}
int find(int p){
	access(p);
	splay(p);
	pushdown(p);
	while(ch[p][0])p=ch[p][0],pushdown(p);
	splay(p);
	return p;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=m;i++){
		int xp;cin>>xp;
		int x,y;cin>>x>>y; 
		if(xp==0)split(x,y),cout<<size[y]<<endl;
		else if(xp==1)link(x,y);
		else if(xp==2)cut(x,y);
		else if(xp==3)splay(x),w[x]=y;
	}
}