重置一发LCT模板

加边、删边、单点修改、链上异或和

#include <bits/stdc++.h>
using namespace std;
inline void read(int &num) {
	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg = -flg;
	for(num=0; isdigit(ch); num=num*10+ch-'0', ch=getchar()); num*=flg;
}
const int MAXN = 100005;
int fa[MAXN], ch[MAXN][2], sum[MAXN], val[MAXN];
bool rev[MAXN];
inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return ch[fa[x]][1] == x; }
inline void upd(int x) { sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x]; }
inline void mt(int x) { if(rev[x]) rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1, swap(ch[x][0], ch[x][1]), rev[x] = 0; }
void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }
inline void rot(int x) {
	int y = fa[x], z = fa[y]; bool l = get(x), r = l^1;
	if(!isr(y)) ch[z][get(y)] = x;
	fa[ch[x][r]] = y, fa[y] = x, fa[x] = z;
	ch[y][l] = ch[x][r], ch[x][r] = y;
	upd(y), upd(x);
}
inline void splay(int x) {
	mtpath(x);
	for(; !isr(x); rot(x))
		if(!isr(fa[x])) rot(get(fa[x]) == get(x) ? fa[x] : x);
}
inline int access(int x) { int y = 0;
	for(; x; x = fa[y=x])
		splay(x), ch[x][1] = y, upd(x);
	return y;
}
inline int sert(int x) { int X = x;
	access(x), splay(x);
	while(ch[x][0])x=ch[x][0];
	splay(x), splay(X);
	return x;
}
inline void Top(int x) { access(x), splay(x); }
inline void bert(int x) { Top(x), rev[x] ^= 1; }
inline int split(int x, int y) { bert(x), Top(y); return y; }
inline void link(int x, int y) { bert(x); if(sert(y) != x) fa[x] = y; }
inline void cut(int x, int y) { bert(x); if(sert(y) == x && fa[x] == y && !ch[x][1]) fa[x] = ch[y][0] = 0; }
inline void modify(int x, int wt) { bert(x), val[x] = wt, upd(x); }
inline int qsum(int x, int y) { return sum[split(x, y)]; }
int n, m;
int main () {
	read(n), read(m);
	for(int i = 1; i <= n; ++i) read(val[i]), sum[i] = val[i];
	int op, x, y;
	while(m--) {
		read(op), read(x), read(y);
		switch(op) {
			case 0: printf("%d
", qsum(x, y)); break;
			case 1: link(x, y); break;
			case 2: cut(x, y); break;
			case 3: modify(x, y); break;
		}
	}
}