<span>LCT板子</span>

#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int fa[N], ch[N][2], sum[N], val[N], rev[N];
inline void update(int x) { sum[x] = sum[ls(x)] ^ sum[rs(x)] ^ val[x]; }
inline int nroot(int x) { return ls(fa[x]) == x || rs(fa[x]) == x; }
inline int get(int x) { return rs(fa[x]) == x; }
inline void rotate(int x) {
	int y = fa[x], z = fa[y], k = get(x), w = ch[x][!k];
	if(nroot(y)) ch[z][get(y)] = x; ch[x][!k] = y; ch[y][k] = w;
	if(w) fa[w] = y; fa[y] = x; fa[x] = z; update(y);
}
inline void pushdown(int x) {
	if(rev[x]) {swap(ls(x), rs(x));
		if(ls(x)) rev[ls(x)] ^= 1; if(rs(x)) rev[rs(x)] ^= 1;
		 rev[x] = 0;
	}
}
inline void pushall(int x) { if(nroot(x)) pushall(fa[x]); pushdown(x); }
inline void splay(int x) {
	pushall(x);
	while(nroot(x)) {
		if(nroot(fa[x])) rotate(get(x) ^ get(fa[x]) ? x : fa[x]);
		rotate(x);
	} update(x);
}
inline void access(int x) {
	for(R int y = 0; x; x = fa[y = x]) splay(x), rs(x) = y, update(x);
}
inline void makeroot(int x) { access(x); splay(x); rev[x] ^= 1; }
inline void split(int x, int y) { makeroot(x); access(y); splay(y); }
inline int findroot(int x) {
	access(x); splay(x); while(ls(x)) pushdown(x), x = ls(x); splay(x); return x;
}
inline void link(int x, int y) {
	makeroot(x);  if(findroot(y) != x) fa[x] = y, update(y);
}
inline void cut(int x, int y) {
	makeroot(x);
	if(findroot(y) == x && fa[y] == x && ls(y) == 0) ch[x][1] = fa[y] = 0, update(x);
}