什么都不想写了，
看大佬们的博客吧QAQ
题目背景
动态树
题目描述
给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。
0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。
1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。
2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。
3：后接两个整数(x，y)，代表将点x上的权值变成y。
输入格式
第1行两个整数，分别为n和m，代表点数和操作数。
第2行到第n+1行，每行一个整数，整数在［1，10^9］内，代表每个点的权值。
第n+2行到第n+m+1行，每行三个整数，分别代表操作类型和操作所需的量。
输出格式
对于每一个0号操作，你须输出x到y的路径上点权的xor和。
输入输出样例
putin
3 3 1231 1 20 1 2 0 1 1
putout
3
1
#include#define re return#define ls c[x][0]#define rs c[x][1] #define Ri register int#define inc(i,l,r) for(int i=l;i<=r;++i)const int maxn=3e5+5;using namespace std;template inline void rd(T&x){ char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1l; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x;}int q[maxn],n,m,c[maxn][2],val[maxn],ans[maxn],f[maxn];bool rev[maxn];inline bool nrt(int x){ re c[f[x]][0]==x||c[f[x]][1]==x;}inline void pushup(int x){ ans[x]=ans[ls]^ans[rs]^val[x];}inline void filp(int x){ rev[x]^=1; swap(ls,rs);}inline void pushrev(int x){ if(!rev[x])re; rev[x]=0; if(ls)filp(ls); if(rs)filp(rs);}inline void rotate(int x){ int y=f[x],z=f[y],k=(c[y][1]==x),w=c[x][!k]; if(nrt(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w; if(w)f[w]=y;f[x]=z;f[y]=x; pushup(y),pushup(x);}inline void splay(int x){ int y=x,top=0;q[++top]=y; while(nrt(y))q[++top]=y=f[y]; while(top)pushrev(q[top--]); while(nrt(x)) { y=f[x],top=f[y]; if(nrt(y)) ((c[y][0]==x)&&(c[top][0]==y))?rotate(y):rotate(x); rotate(x); } //pushup(x)}inline void Access(int x)//将x->rt改为实边 { for(Ri y=0;x;x=f[y=x]) { splay(x); c[x][1]=y; pushup(x); }}inline void makert(int x)//使rt变为rt { Access(x);splay(x); filp(x);//降低复杂度 }inline int findrt(int x)//寻找根节点 { Access(x);splay(x); while(ls)pushrev(x),x=ls; re x;}inline void split(int x,int y)//将x,y弄到同一棵splay { makert(x);Access(y);splay(y);}inline void link(int x,int y){ makert(x); if(findrt(y)!=x)f[x]=y; }inline void cut(int x,int y){ split(x,y); if(findrt(y)!=x||f[x]!=y||rs) re; else { f[x]=c[y][0]=0; pushup(y); }}int main(){ int opt,x,y; rd(n),rd(m); inc(i,1,n)rd(val[i]); inc(i,1,m) { rd(opt);rd(x),rd(y); switch(opt){ case 0:split(x,y);printf("%d\n",ans[y]);break; case 1:link(x,y);break; case 2:cut(x,y);break; case 3:splay(x);val[x]=y;break; } } re 0;}