LCT板子23分求调悬关

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

const int MAXN = 100005;

int n, m;

namespace Link_cut_Tree {
#define lc ch[u][0]
#define rc ch[u][1]
int val[MAXN], s[MAXN];
int fa[MAXN], ch[MAXN][2];
int tg[MAXN];
inline bool isroot(int u) {
	return ch[fa[u]][0] != u && ch[fa[u]][1] != u;
}
inline void push_up(int u) {
	s[u] = val[u] ^ s[lc] ^ s[rc];
}
inline void Reverse(int u) {
	swap(lc, rc);
	tg[u] ^= 1;
}
inline void push_down(int u) {
	if (!tg[u]) return;
	if (lc) Reverse(lc);
	if (rc) Reverse(rc);
	tg[u] = 0;
}
inline void Rotate(int u) {
	int fath = fa[u];
	int g_fa = fa[fath];
	int k = ch[fath][1] == u;
	fa[u] = g_fa;
	if (!isroot(fath))
		ch[g_fa][ch[g_fa][1] == fath] = u;
	if (ch[u][!k]) fa[ch[u][!k]] = fath;
	ch[fath][k] = ch[u][!k];
	ch[u][!k] = fath, fa[fath] = u;
	push_up(fath);
}
inline void pushll(int u) {
	if (!isroot(u)) pushll(fa[u]);
	push_down(u);
}
inline void Splay(int u) {
	pushll(u);
	int fath, g_fa;
	if (!isroot(u)) {
		fath = fa[u], g_fa = fa[fath];
		if (!isroot(fath))
			Rotate(((ch[fath][1] == u) ^ (ch[g_fa][1] == fath)) ? u : fath);
		Rotate(u);
	} 
	push_up(u);
}
inline void access(int u) {
	for (int son = 0; u; u = fa[son = u])
		Splay(u), rc = son, push_up(u);
}
inline void makeroot(int u) {
	access(u); Splay(u);
	Reverse(u);
}
inline int findroot(int u) {
	makeroot(u);
	while (lc) push_down(u), u = lc;
	Splay(u); return u;
}
inline void Split(int u, int v) {
	makeroot(u);
	access(v); Splay(v);
}
inline void Link(int u, int v) {
	makeroot(u);
	if (findroot(v) != u) fa[u] = v;
}
inline void cut(int u, int v) {
	makeroot(u);
	if (findroot(v) == u && fa[v] == u && !ch[v][0]) {
		fa[v] = ch[u][1] = 0;
		push_up(u);
	}
}
#undef lc
#undef rc
} 
using namespace Link_cut_Tree;

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i)
		scanf ("%d", val + i);
	int op, x, y;
	while (m --) {
		scanf ("%d%d%d", &op, &x, &y);
		switch(op) {
		case 0 : Split(x, y); printf ("%d\n", s[y]); break;
		case 1 : Link(x, y); break;
		case 2 : cut(x, y); break;
		case 3 : Splay(x); val[x] = y; push_up(x);
		}
	}
	return 0;
}