LCT板子

二十行舒舒服服。

int ch[N][2], fa[N], val[N], s[N], tag[N];
#define lc ch[x][0]
#define rc ch[x][1]
il void upd(int x) {s[x] = val[x] ^ s[lc] ^ s[rc];}
il void rev(int x) {tag[x] ^= 1, swap(lc, rc);}
void psd(int x) {if (tag[x]) rev(lc), rev(rc), tag[x] = 0;}
il bool son(int x) {return ch[fa[x]][1] == x;}
il bool nroot(int x) {return ch[fa[x]][0] == x || ch[fa[x]][1] == x;}
void rotate(int x) {
    int y = fa[x], z = fa[y], w = !son(x), o = ch[x][w]; ch[y][w ^ 1] = o; if (o) fa[o] = y;
    if (nroot(y)) ch[z][son(y)] = x; fa[x] = z; fa[y] = x; ch[x][w] = y; upd(y); upd(x);    
} void dfs(int x) {if (nroot(x)) dfs(fa[x]); psd(x);}
void splay(int x) {for (dfs(x); nroot(x); rotate(x)) if (nroot(fa[x])) son(x) ^ son(fa[x]) ? rotate(x) : rotate(fa[x]);} 
void access(int x) {for (int y = 0; x; x = fa[y = x]) splay(x), ch[x][1] = y, upd(x);} 
void makeroot(int x) {access(x); splay(x); rev(x);}
int findroot(int x) {access(x); splay(x); while (lc) psd(x = lc); splay(x); return x;}
void link(int x, int y) {makeroot(x); if (findroot(y) != x) fa[x] = y;}
void cut(int x, int y) {makeroot(x); if (findroot(y) != x || rc != y) return ; fa[y] = ch[x][1] = 0; upd(x);}
void modify(int x, int d) {makeroot(x); val[x] = d; upd(x);}
void query(int x, int y) {makeroot(x); access(y); splay(y); pr2(s[y]);}