[luoguP3690] 【模板】Link Cut Tree

处理路径 xor 和的时候可以维护子树 xor 和，先提取出路径，再把一个点 splay 到最上方，直接取子树 xor 和即可。
更新一个点权时可以先提取出根到这个点的路径，把这个点 splay 到最上方，然后 update 即可。
——代码
  1 #include <cstdio>
  2 #include <iostream>
  3 #define N 300001
  4 #define get(x) (son[f[x]][1] == (x))
  5 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
  6 #define isroot(x) (son[f[x]][0] ^ (x) && son[f[x]][1] ^ (x))
  7 
  8 int n, m;
  9 int a[N], sum[N], son[N][2], rev[N], f[N], s[N];
 10 
 11 inline int read()
 12 {
 13     int x = 0, f = 1;
 14     char ch = getchar();
 15     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
 16     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
 17     return x * f;
 18 }
 19 
 20 inline void update(int x)
 21 {
 22     if(x)
 23     {
 24         sum[x] = a[x];
 25         if(son[x][0]) sum[x] ^= sum[son[x][0]];
 26         if(son[x][1]) sum[x] ^= sum[son[x][1]];
 27     }
 28 }
 29 
 30 inline void pushdown(int x)
 31 {
 32     if(x && rev[x])
 33     {
 34         swap(son[x][0], son[x][1]);
 35         if(son[x][0]) rev[son[x][0]] ^= 1;
 36         if(son[x][1]) rev[son[x][1]] ^= 1;
 37         rev[x] = 0;
 38     }
 39 }
 40 
 41 inline void rotate(int x)
 42 {
 43     int old = f[x], oldf = f[old], wh = get(x);
 44     
 45     if(!isroot(old))
 46         son[oldf][get(old)] = x;
 47     f[x] = oldf;
 48     
 49     son[old][wh] = son[x][wh ^ 1];
 50     f[son[old][wh]] = old;
 51     
 52     son[x][wh ^ 1] = old;
 53     f[old] = x;
 54     
 55     update(old);
 56     update(x);
 57 }
 58 
 59 inline void splay(int x)
 60 {
 61     int i, fa, t = 0;
 62     s[++t] = x;
 63     for(i = x; !isroot(i); i = f[i]) s[++t] = f[i];
 64     for(i = t; i >= 1; i--) pushdown(s[i]);
 65     for(; !isroot(x); rotate(x))
 66         if(!isroot(fa = f[x]))
 67             rotate(get(x) ^ get(fa) ? x : fa);
 68 }
 69 
 70 inline void access(int x)
 71 {
 72     for(int t = 0; x; t = x, x = f[x]) splay(x), son[x][1] = t, update(x);
 73 }
 74 
 75 inline void reverse(int x)
 76 {
 77     access(x);
 78     splay(x);
 79     rev[x] ^= 1;
 80 }
 81 
 82 inline int query(int x, int y)
 83 {
 84     reverse(x);
 85     access(y);
 86     splay(y);
 87     return sum[y];
 88 }
 89 
 90 inline int find(int x)
 91 {
 92     access(x);
 93     splay(x);
 94     while(son[x][0]) x = son[x][0];
 95     return x;
 96 }
 97 
 98 inline void link(int x, int y)
 99 {
100     reverse(x);
101     f[x] = y;
102     access(x);
103 }
104 
105 inline void cut(int x, int y)
106 {
107     reverse(x);
108     access(y);
109     splay(y);
110     son[y][0] = f[x] = 0;
111     update(y);
112 }
113 
114 inline void change(int x, int y)
115 {
116     access(x);
117     splay(x);
118     a[x] = y;
119     update(x);
120 }
121 
122 int main()
123 {
124     int i, x, y, z;
125     n = read();
126     m = read();
127     for(i = 1; i <= n; i++) a[i] = read();
128     for(i = 1; i <= m; i++)
129     {
130         z = read();
131         x = read();
132         y = read();
133         if(z == 0) printf("%d
", query(x, y));
134         if(z == 1)
135             if(find(x) ^ find(y))
136                 link(x, y);
137         if(z == 2)
138             if(find(x) == find(y))
139                 cut(x, y);
140         if(z == 3) change(x, y);
141     }
142 }
View Code