题目链接：SPOJ 2939

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

• 0 i：反转点 $i$ 的颜色（黑色变成白色，白色变成黑色）。
• 1 v：询问 $\min\{\text{dist}(u, v)\}$，其中点 $u$ 必须是白点，两个点可以相同。显然如果点 $v$ 是白色的，那么答案一定是 $0$。特殊地，如果树上不存在白点，那么输出 $-1$。

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

Solution

很显然本题是 SPOJ 2666（题解）的弱化版，于是我们就可以愉快地搬代码啦！QAQ

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

Code

#include <cstdio>
#include <algorithm>
#include <set>

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

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

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int len, sum, lmn, rmn;
    bool col;
    std::multiset<int> down;
    Node() {
        ch[0] = ch[1] = fa = null;
        len = sum = lmn = rmn = col = 0;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void pushup() {
        sum = ch[0]->sum + ch[1]->sum + len;
        int t = std::min(col ? INF : 0, down.empty() ? INF : *down.begin());
        int L = std::min(t, ch[0]->rmn + len);
        int R = std::min(t, ch[1]->lmn);
        lmn = std::min(ch[0]->lmn, ch[0]->sum + len + R);
        rmn = std::min(ch[1]->rmn, ch[1]->sum + L);
    }
} *a[N];

struct LCT {
    LCT() {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
        null->lmn = null->rmn = INF;
    }
    void build(int n) {
        for (int i = 1; i <= n; i++) {
            a[i] = new Node();
            a[i]->col = 1;
        }
    }
    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);
            if (x->ch[1] != null) {
                x->down.insert(x->ch[1]->lmn);
            }
            if ((x->ch[1] = y) != null) {
                x->down.erase(x->down.find(y->lmn));
            }
            x->pushup();
        }
    }
};

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;
        a[v]->fa = a[u];
        a[v]->len = 1;
        dfs(v, u);
        a[u]->down.insert(a[v]->lmn);
    }
    a[u]->pushup();
}
int main() {
    scanf("%d", &n);
    LCT T;
    T.build(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(1, 0);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        T.access(a[x]), T.splay(a[x]);
        if (!opt) {
            a[x]->col ^= 1;
            a[x]->pushup();
        } else {
            int ans = a[x]->rmn;
            if (ans >= INF) {
                puts("-1");
            } else {
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}