一位大佬写的代码。（加上我自己的一些习惯性写法）
存个模板。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+5;
4 int n,m,a[N],w[N];
5 struct node{
6 int fa,lc,rc,rv;
7 #define lc(x) t[x].lc
8 #define rc(x) t[x].rc
9 #define fa(x) t[x].fa
10 #define rv(x) t[x].rv
11 }t[N];
12
13 void up(int x){
14 w[x]=a[x]^w[lc(x)]^w[rc(x)];
15 }
16
17 bool isr(int x)//isroot
18 {
19 return lc(fa(x))!=x&&rc(fa(x))!=x;
20 }
21 bool wrt(int x){
22 return rc(fa(x))==x;
23 }
24
25 void rev(int x){//做标记
26 if(!x) return;
27 swap(lc(x),rc(x));
28 rv(x)^=1;
29 }
30
31 void down(int x){//下传标记
32 if(rv(x)){
33 rev(lc(x)),rev(rc(x));
34 }
35 rv(x)=0;
36 }
37
38 void rot(int x){//旋转
39 int y=fa(x),z=fa(y),b=(lc(y)==x)?rc(x):lc(x);
40 if(z&&!isr(y)) (lc(z)==y?lc(z):rc(z))=x;
41 fa(x)=z,fa(y)=x;
42 if(b) fa(b)=y;
43 if(lc(y)==x) rc(x)=y,lc(y)=b;
44 else lc(x)=y,rc(y)=b;
45 up(y),up(x);
46 }
47
48 void path(int x){//根到节点上的点都下传标记
49 if(!isr(x)) path(fa(x));
50 down(x);
51 }
52
53 void spl(int x){//splay
54 path(x);
55 while(!isr(x)){
56 if(!isr(fa(x))) wrt(x)==wrt(fa(x))?rot(fa(x)):rot(x);
57 rot(x);
58 }
59 }
60
61 void acs(int x){
62 for(int y=0;x;y=x,x=fa(x)){
63 spl(x),rc(x)=y,up(x);
64 }
65 }
66
67 void mrt(int x){//makeroot
68 acs(x),spl(x),rev(x);
69 }
70
71 int fnd(int x){//findroot
72 acs(x),spl(x),down(x);
73 while(lc(x)) x=lc(x),down(x);
74 spl(x);return x;
75 }
76
77 void lk(int x,int y){//link
78 mrt(x);
79 if(fnd(y)==x) return ;
80 fa(x)=y;
81 }
82
83 void cut(int x,int y){//删边
84 mrt(x),acs(y),spl(y);
85 if(lc(y)!=x) return ;
86 lc(y)=fa(x)=0;
87 }
88
89 int main(){
90 scanf("%d%d",&n,&m);
91 for(int i=1;i<=n;i++){
92 scanf("%d",&a[i]),w[i]=a[i];
93 }
94 for(int i=1;i<=m;i++){
95 int o,x,y;
96 scanf("%d%d%d",&o,&x,&y);
97 if(o==0){
98 mrt(x),acs(y),spl(y);//提取x到y的路径
99 cout<<w[y]<<endl;
100 }
101 if(o==1) lk(x,y);
102 if(o==2) cut(x,y);
103 if(o==3) acs(x),spl(x),a[x]=y,up(x);
104 }
105 return 0;
106 }
