https://www.luogu.org/problem/P3690
知识点：
#include <bits/stdc++.h> using namespace std; int n,m; struct node { int fa; int ch[2]; int sum; int val; int lazy; }t[310000]; bool root(int x) { int g = t[x].fa; return !((t[g].ch[0] == x)||(t[g].ch[1] == x)); } void pushup(int x) { int l = t[x].ch[0],r = t[x].ch[1]; t[x].sum = t[x].val ^ t[l].sum ^ t[r].sum; } inline void pushr(int x) { if(!x)return; swap(t[x].ch[0],t[x].ch[1]); t[x].lazy ^= 1; } void pushdown(int x) { if(t[x].lazy) { pushr(t[x].ch[0]); pushr(t[x].ch[1]); t[x].lazy = 0; } } void push(int x) { if(!root(x))push(t[x].fa); pushdown(x); } void rotate(int x) { int y = t[x].fa; int z = t[y].fa; int k = t[y].ch[1] == x; if(!root(y)) t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z; t[y].ch[k] = t[x].ch[k ^ 1]; if(t[x].ch[k ^ 1])t[t[x].ch[k ^ 1]].fa = y; t[y].fa = x; t[x].ch[k ^ 1] = y; pushup(y);pushup(x); } void splay(int x) { int y,z; push(x); while(!root(x)) { y = t[x].fa,z = t[y].fa; if(!root(y)) { (t[z].ch[0] == y) ^ (t[y].ch[0] == x)?rotate(x):rotate(y); } rotate(x); } pushup(x); } void access(int x) { for(int y = 0;x;y = x,x = t[x].fa) { splay(x);t[x].ch[1] = y;pushup(x); } } void makeroot(int x) { access(x);splay(x); pushr(x); } void split(int x,int y) { makeroot(x); access(y); splay(y); } void link(int x,int y) { makeroot(x); t[x].fa = y; } void cut(int x,int y) { makeroot(x); access(y); splay(y); if(t[y].ch[0] != x || t[x].ch[1])return; t[x].fa = t[y].ch[0] = 0; pushup(x); } int main() { scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) { scanf("%d",&t[i].val); t[i].sum = t[i].val; } int opt,a,b; while(m--) { scanf("%d%d%d",&opt,&a,&b); switch(opt) { case 0: { if(a == b) { printf("%d ",t[a].val); break; } split(a,b); pushup(b); printf("%d ",t[b].sum); break; } case 1: { link(a,b); break; } case 2: { cut(a,b); break; } case 3: { splay(a); t[a].val = b; pushup(a); break; } } } return 0; }