LCT简单介绍
LCT复杂介绍

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;

struct node {
	int ch[2], fa, val;
	int res, tag;
} tree[N];

int Get(int x) {
	return x == tree[tree[x].fa].ch[1];
}

int isroot(int x) {
	return tree[tree[x].fa].ch[0] != x && tree[tree[x].fa].ch[1] != x;
}

void pushup(int x) {
	tree[x].res = tree[tree[x].ch[0]].res ^ tree[tree[x].ch[1]].res ^ tree[x].val;
}

void pushdown(int x) {
	if (tree[x].tag) {
		swap(tree[tree[x].ch[0]].ch[0], tree[tree[x].ch[0]].ch[1]);
		swap(tree[tree[x].ch[1]].ch[0], tree[tree[x].ch[1]].ch[1]);
		tree[tree[x].ch[0]].tag ^= 1;
		tree[tree[x].ch[1]].tag ^= 1;
		tree[x].tag = 0;
	}
}

void update(int x) {
	if (!isroot(x))
		update(tree[x].fa);
	pushdown(x);
}

void rotate(int x) {
	int y = tree[x].fa, z = tree[y].fa, chk = Get(x);
	if (!isroot(y))
		tree[z].ch[y == tree[z].ch[1]] = x;
	tree[x].fa = z;
	tree[y].ch[chk] = tree[x].ch[chk ^ 1];
	if (tree[x].ch[chk ^ 1])
		tree[tree[x].ch[chk ^ 1]].fa = y;
	tree[x].ch[chk ^ 1] = y;
	tree[y].fa = x;
	pushup(y);
	pushup(x);
}

void splay(int x) {
	update(x);
	while (!isroot(x)) {
		int y = tree[x].fa;
		if (!isroot(y)) {
			if (Get(x) == Get(y))
				rotate(y);
			else
				rotate(x);
		}
		rotate(x);
	}
	pushup(x);
}

void access(int x) {
	for (int y = 0; x; y = x, x = tree[x].fa) {
		splay(x);
		tree[x].ch[1] = y;
		pushup(x);
	}
}

void makeroot(int x) {
	access(x);
	splay(x);
	swap(tree[x].ch[0], tree[x].ch[1]);
	tree[x].tag ^= 1;
}

int findroot(int x) {
	access(x);
	splay(x);
	while (tree[x].ch[0])
		pushdown(x), x = tree[x].ch[0];
	splay(x);
	return x;
}

void link(int x, int y) {
	makeroot(x);
	if (findroot(y) != x) {
		splay(x);
		tree[x].fa = y;
	}
}

void cut(int x, int y) {
	makeroot(x);
	if (findroot(y) == x && tree[y].fa == x && tree[y].ch[0] == 0) {
		tree[x].ch[1] = 0;
		tree[y].fa = 0;
		pushup(x);
	}
}

void split(int x, int y) {
	makeroot(x);
	access(y);
	splay(y);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> tree[i].val;
	}
	for (int i = 1; i <= m; i++) {
		int pos, x, y;
		cin >> pos >> x >> y;
		if (pos == 0) {
			split(x, y);
			cout << tree[y].res << endl;
		} else if (pos == 1) {
			link(x, y);
		} else if (pos == 2) {
			cut(x, y);
		} else {
			splay(x);
			tree[x].val = y;
			pushup(x);
		}
	}
	return 0;
}