题目链接：SPOJ 16549

给定一棵 $n$ 个节点的树，初始状态所有点都是黑色的。接下来有 $m$ 个操作，操作分为如下 $2$ 种：

• 0 u：询问有多少个点和 $u$ 连通，两个点是连通的当且仅当 $u, v$ 的路径上（包括 $u, v$）的点的颜色都是相同的。
• 1 u：反转点 $u$ 的颜色（黑色变成白色，白色变成黑色）。

数据范围：$1\le n, m\le 10 ^ 5$。

Solution

如果我们暴力连边、断边，发现直接用一个菊花图就卡掉了。由于每个点只有一条父边，那么我们对每个颜色分别建立一棵 $\text{LCT}$，假设第 $u$ 个点的父边为 $i$，那么在第 $j$ 棵 $\text{LCT}$ 中的边 $i$ 存在当且仅当节点 $u$ 的颜色为 $j$。这样一来我们发现，反转一个点的颜色只需要修改一条边就行了。

接下来考虑如何查询。对于一个连通块内的点，只有其根节点是不确定颜色的，我们直接判断其颜色是否和点 $u$ 相同即可。

考虑如何建边删边？由于我们要维护一个点在原树上的父亲，因此不能使用 makeroot 操作，具体 link 和 cut 详见代码。

时间复杂度：$\mathcal O((n + m) \log n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5, M = 2e5 + 5;

int n, m, tot, lnk[N], ter[M], nxt[M], fa[N];
bool col[N];

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int sz, si, idx;
    Node(int _idx = 0) {
        ch[0] = ch[1] = fa = null;
        sz = si = 0, idx = _idx;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void pushup() {
        sz = ch[0]->sz + ch[1]->sz + si + 1;
    }
};

struct LCT {
    Node *a[N];
    bool C;
    void build(int n) {
        a[0] = new Node(), a[0] = null;
        for (int i = 1; i <= n; i++) {
            a[i] = new Node(i);
        }
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x);
            x->si += x->ch[1]->sz;
            x->si -= (x->ch[1] = y)->sz;
            x->pushup();
        }
    }
    Node *findroot(Node *x) {
        access(x), splay(x);
        while (x->ch[0] != null) x = x->ch[0];
        splay(x);
        return x;
    }
    void link(Node *x, Node *y) {
        if (y == null) return;
        access(y), splay(y), splay(x);
        (x->fa = y)->si += x->sz;
        y->pushup();
    }
    void cut(Node *x, Node *y) {
        if (y == null) return;
        access(x), splay(x);
        x->ch[0] = x->ch[0]->fa = null;
        x->pushup();
    }
    int query(Node *x) {
        Node *f = findroot(x);
        if (col[f->idx] == C) {
            return f->sz;
        } else {
            return f->ch[1]->sz;
        }
    }
} T[2];

void init() {
    null = new Node();
    null->ch[0] = null->ch[1] = null->fa = null;
    T[0].build(n), T[0].C = 0;
    T[1].build(n), T[1].C = 1;
    for (int i = 1; i <= n; i++) {
        T[1].link(T[1].a[i], T[1].a[fa[i]]);
    }
}
void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        fa[v] = u;
        dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        col[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    init();
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int opt, u;
        scanf("%d%d", &opt, &u);
        bool &c = col[u];
        if (!opt) {
            printf("%d\n", T[c].query(T[c].a[u]));
        } else {
            T[c].cut(T[c].a[u], T[c].a[fa[u]]);
            c ^= 1;
            T[c].link(T[c].a[u], T[c].a[fa[u]]);
        }
    }
    return 0;
}