SPOJ_2798
如果用link-cut-tree写的话，只要维护col（节点的颜色）和sum（子树中black节点的数量）两个标记即可。染色的时候将对应节点splay到根然后修改，查询的时候先进行access(v)的操作，之后找到这棵splay的根再递归查找即可，如果根结点的sum值为0，则输出-1。
#include#include #define MAXD 100010#define MAXM 200010int N, Q, q[MAXD], first[MAXD], e, next[MAXM], v[MAXM];struct Splay{ int pre, ls, rs, col, sum; bool root; void update(); void zig(int ); void zag(int ); void splay(int ); void renew() { root = true; pre = ls = rs = 0; col = 0, sum = 0; }}sp[MAXD];void Splay::update(){ sum = sp[ls].sum + sp[rs].sum + col;}void Splay::zig(int x){ int y = rs, fa = pre; rs = sp[y].ls, sp[rs].pre = x; sp[y].ls = x, pre = y; sp[y].pre = fa; if(root) root = false, sp[y].root = true; else sp[fa].rs == x ? sp[fa].rs = y : sp[fa].ls = y; update();}void Splay::zag(int x){ int y = ls, fa = pre; ls = sp[y].rs, sp[ls].pre = x; sp[y].rs = x, pre = y; sp[y].pre = fa; if(root) root = false, sp[y].root = true; else sp[fa].rs == x ? sp[fa].rs = y : sp[fa].ls = y; update();}void Splay::splay(int x){ int y, z; for(; !root;) { y = pre; if(sp[y].root) sp[y].rs == x ? sp[y].zig(y) : sp[y].zag(y); else { z = sp[y].pre; if(sp[z].rs == y) { if(sp[y].rs == x) sp[z].zig(z), sp[y].zig(y); else sp[y].zag(y), sp[z].zig(z); } else { if(sp[y].ls == x) sp[z].zag(z), sp[y].zag(y); else sp[y].zig(y), sp[z].zag(z); } } } update();}void add(int x, int y){ v[e] = y; next[e] = first[x], first[x] = e ++;}void prepare(){ int i, j, x, rear = 0; sp[0].sum = 0; q[rear ++] = 1; sp[1].renew(); for(i = 0; i < rear; i ++) { x = q[i]; for(j = first[x]; j != -1; j = next[j]) if(v[j] != sp[x].pre) { sp[v[j]].renew(), sp[v[j]].pre = x; q[rear ++] = v[j]; } }}void init(){ int i, x, y; memset(first, -1, sizeof(first)); e = 0; for(i = 1; i < N; i ++) { scanf("%d%d", &x, &y); add(x, y), add(y, x); } prepare();}void change(int x){ sp[x].splay(x); sp[x].col ^= 1; sp[x].update();}void access(int x){ int fx; for(fx = x, x = 0; fx != 0; x = fx, fx = sp[x].pre) { sp[fx].splay(fx); sp[sp[fx].rs].root = true; sp[fx].rs = x, sp[x].root = false; sp[fx].update(); }}int Search(int cur){ if(sp[sp[cur].ls].sum != 0) return Search(sp[cur].ls); else if(sp[cur].col) return cur; else return Search(sp[cur].rs);}void ask(int x){ int y; access(x); for(y = x; !sp[y].root; y = sp[y].pre); if(sp[y].sum == 0) printf("-1\n"); else printf("%d\n", Search(y));}void solve(){ int i, op, x; for(i = 0; i < Q; i ++) { scanf("%d%d", &op, &x); if(op == 0) change(x); else ask(x); }}int main(){ while(scanf("%d%d", &N, &Q) == 2) { init(); solve(); } return 0;}