[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 19 20 inline void update(int x) 21 28 } 29 30 inline void pushdown(int x) 31 39 } 40 41 inline void rotate(int x) 42 58 59 inline void splay(int x) 60 69 70 inline void access(int x) 71 74 75 inline void reverse(int x) 76 81 82 inline int query(int x, int y) 83 89 90 inline int find(int x) 91 97 98 inline void link(int x, int y) 99 104 105 inline void cut(int x, int y) 106 113 114 inline void change(int x, int y) 115 121 122 int main() 123 142 }
View Code

上一篇：[luoguP1280] 尼克的任务（DP）

下一篇：[luoguP3047] [USACO12FEB]附近的牛Nearby Cows（DP）

---

模板 LCT