[模板] Link Cut Tree （动态树）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;

int n, m;
int st[N];
struct node {
	int val;
	int fa;
	int ch[2];
	bool r;
	int sum;
} t[N];

inline int read() {
	int x = 0; char c = getchar(); bool f = 1;
	while(c < '0' || c > '9') { if(c == '-') f = !f; c = getchar(); }
	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	return f ? x : -x;
}
bool nroot(int x) {
	return t[t[x].fa].ch[1] == x || t[t[x].fa].ch[0] == x;
}
void push_up(int x) {
	t[x].sum = t[t[x].ch[0]].sum ^ t[t[x].ch[1]].sum ^ t[x].val;
}
void push_r(int x) {
	swap(t[x].ch[0], t[x].ch[1]);
	t[x].r ^= 1;
}
void push_down(int x) {
	if(t[x].r) {
		if(t[x].ch[0]) push_r(t[x].ch[0]);
		if(t[x].ch[1]) push_r(t[x].ch[1]);
		t[x].r = 0;
	}
}
void rotate(int x) {
	int y = t[x].fa;
	int z = t[y].fa;
	int k = t[y].ch[1] == x;
	if(nroot(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[x].ch[k ^ 1] = y;
	t[y].fa = x;
	push_up(y);
}
void Splay(int x) {
	int y = x, z = 0;
	st[++z] = y;
	while(nroot(y)) st[++z] = y = t[y].fa;
	while(z) push_down(st[z--]);
	while(nroot(x)) {
		y = t[x].fa;
		z = t[y].fa;
		if(nroot(y)) 
			(t[y].ch[0] == x) ^ (t[z].ch[0] == y) ? rotate(x) : rotate(y);
		rotate(x);
	}
	push_up(x);
}
void access(int x) {
	for(int y = 0; x; y = x, x = t[x].fa)
		Splay(x), t[x].ch[1] = y, push_up(x);
}
void makeroot(int x) {
	access(x); Splay(x);
	push_r(x);
}
int findroot(int x) {
	access(x); Splay(x);
	while(t[x].ch[0]) push_down(x), x = t[x].ch[0];
	Splay(x);//一定要加这个 ! ! ! 不然cut中会出错a
	return x;
}
void split(int x, int y) {
	makeroot(x);
	access(y); Splay(y);
}
void link(int x, int y) {
	makeroot(x);
	if(findroot(y) != x) t[x].fa = y;
}
void cut(int x, int y) {
	makeroot(x);
	if(findroot(y) == x && t[y].fa == x && !t[y].ch[0]) {//要先findroot...  如果y有左儿子则x应先接y的左儿子(~~好像是的趴~~
		t[y].fa = t[x].ch[1] = 0;
		push_up(x);
	}
}
int main() {
	n = read(); m = read();
	for(int i = 1; i <= n; i++) t[i].val = read();
	for(int i = 1; i <= m; i++) {
		int opt, x, y;
		opt = read(); x = read(); y = read();
		if(opt == 0) {
			split(x, y);
			printf("%d
", t[y].sum);
		}
		else if(opt == 1) link(x, y);
		else if(opt == 2) cut(x, y);
		else Splay(x), t[x].val = y;
	}
	return 0;
}