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

https://www.luogu.org/problemnew/show/P3690
分析：
　　LCT模板
代码：
注意一下cut！
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 char buf[100000],*_p1 = buf,*_p2 = buf;
 6 #define nc() (_p1==_p2&&(_p2=(_p1=buf)+fread(buf,1,100000,stdin),_p1==_p2) ? EOF :*_p1++) 
 7 inline int read() {
 8     int x=0,f=1;char ch=nc();for(;!isdigit(ch);ch=nc())if(ch=='-')f=-1;
 9     for (;isdigit(ch);ch=nc())x=x*10+ch-'0';return x*f;
10 }
11 
12 const int N = 300100;
13 
14 int val[N],fa[N],ch[N][2],rev[N],sum[N],sk[N],Top;
15 
16 inline void pushup(int x) {
17     sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x];
18 }
19 inline void pushdown(int x) {
20     if (rev[x]) {
21         rev[ch[x][0]] ^= 1; rev[ch[x][1]] ^= 1;
22         swap(ch[x][0], ch[x][1]);
23         rev[x] ^= 1;
24     }
25 }
26 inline bool isroot(int x) {
27     return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
28 }
29 inline int son(int x) {
30     return x == ch[fa[x]][1];
31 }
32 inline void rotate(int x) {
33     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
34     if (!isroot(y)) ch[z][c] = x;fa[x] = z;
35     ch[x][!b] = y;fa[y] = x;
36     ch[y][b] = a;if (a) fa[a] = y;
37     pushup(y);pushup(x);
38 }
39 inline void splay(int x) {
40     sk[Top = 1] = x;
41     for (int i=x; !isroot(i); i=fa[i]) sk[++Top] = fa[i];
42     while (Top) pushdown(sk[Top--]);
43     while (!isroot(x)) {
44         int y = fa[x];
45         if (isroot(y)) rotate(x);
46         else {
47             if (son(x) == son(y)) rotate(y), rotate(x);
48             else rotate(x), rotate(x);
49         }
50     }
51 }
52 inline void access(int x) {
53     for (int last=0; x; last=x, x=fa[x]) {
54         splay(x); ch[x][1] = last; pushup(x);
55     }
56 }
57 inline void makeroot(int x) {
58     access(x); splay(x); rev[x] ^= 1;
59 }
60 inline int find(int x) {
61     access(x); splay(x); 
62     while (ch[x][0]) x = ch[x][0];
63     return x;
64 }
65 inline void link(int x,int y) {
66     makeroot(x); 
67     fa[x] = y;
68 }
69 inline void cut(int x,int y) {
70     makeroot(x); access(y); splay(y);
71     if (fa[x] == y && !ch[x][1]) fa[x] = ch[y][0] = 0;
72 }
73 inline void update(int x,int y) {
74     makeroot(x);val[x] = y;pushup(x);
75 }
76 inline int query(int x,int y) {
77     makeroot(x);access(y);splay(y);
78     return sum[y];
79 }
80 int main() {
81     int n = read(),m = read(),opt,x,y;
82     for (int i=1; i<=n; ++i) sum[i] = val[i] = read();
83     while (m--) {
84         opt = read(),x = read(),y = read();
85         if (opt==0) printf("%d
",query(x,y));
86         else if (opt==1) {
87             if (find(x)!=find(y)) link(x,y);
88         }
89         else if (opt==2) {
90             if (find(x)==find(y)) cut(x,y);
91         }
92         else update(x,y);
93     }
94     return 0;
95 }