原理：
https://wenku.baidu.com/view/75906f160b4e767f5acfcedb
http://www.cnblogs.com/flashhu/p/8324551.html
模板题： https://www.luogu.org/problemnew/show/P3690
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
using namespace std;
int val[300005],s[300005];
int ch[300005][2],fa[300005];
bool reversed[300005];
int sta[300005],top;
inline int read() {
char ch=0;int sum=0;
while (ch>'9'||ch<'0') ch=getchar();
while (ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
return sum;
}
inline void reverse(int x) {
swap(ch[x][0],ch[x][1]);//注意使用algorithm
reversed[x]^=1;//若有标记，则已经翻转
}
inline void pushdown(int x) {
if (reversed[x]) {
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
reversed[x]=0;
}
}
inline void pushup(int x) {
s[x]=s[ch[x][0]]^s[ch[x][1]]^val[x];
}
inline bool notroot(int x) {
return (ch[fa[x]][0]==x)||(ch[fa[x]][1]==x);
}
inline void rotate(int x) {
int fa1=fa[x],fa2=fa[fa1],side=(ch[fa1][1]==x),c=ch[x][side^1];
fa[x]=fa2;if (notroot(fa1)) ch[fa2][ch[fa2][1]==fa1]=x;//注意区别以及顺序
ch[fa1][side]=c;if (c) fa[c]=fa1;
fa[fa1]=x;ch[x][side^1]=fa1;
pushup(fa1);pushup(x);
}
inline void splay(int x) {//全部转到根
int u=x,top=0;
while (notroot(u)) sta[++top]=u,u=fa[u];//预先把所有标记下放
sta[++top]=u;
while (top) pushdown(sta[top--]);
while (notroot(x)) {
int fa1=fa[x],fa2=fa[fa1];
if (notroot(fa1)) {//注意区别
if ((ch[fa2][0]==fa1)^(ch[fa1][0]==x)) rotate(x);
else rotate(fa1);
}
rotate(x);
}
}
inline void access(int x) {
int u=0;
while (x!=0) {
splay(x);
ch[x][1]=u;
pushup(x);//别忘
u=x;
x=fa[x];
}
}
inline void makeroot(int x) {
access(x);splay(x);
reverse(x);
}
inline int findroot(int x) {
access(x);splay(x);
while (ch[x][0]) pushdown(x),x=ch[x][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 (findroot(y)!=x) fa[x]=y;//x在findroot(y)后被转到了根
}
inline void cut(int x,int y) {
makeroot(x);
if (findroot(y)==x && fa[y]==x && ch[x][1]==y) {//x在findroot(y)后被转到了根
fa[y]=ch[x][1]=0;
pushup(x);
}
}
int main() {
int n=read(),m=read();
for (int i=1;i<=n;i++) val[i]=read();
while (m--) {
int op=read(),x=read(),y=read();
if (op==0) {
split(x,y);
printf("%d\n",s[y]);
}
else if (op==1) link(x,y);
else if (op==2) cut(x,y);
else if (op==3) {splay(x);val[x]=y;pushup(x);}
}
return 0;
}