문제: https://www.acmicpc.net/problem/13514

어떤 트리가 주어졌을 때, 특정 정점의 색을 반전시키거나 특정 정점에서 가장 가까운 흰색 정점까지의 거리를 찾는 문제다. (query: 1 u / 2 v)

아 일단 센트로이드 디컴포지션을 모른다면 알아서 이거 등 갓들의 블로그에서 잘 배우고 오자.

아래 문제들은 색이 단방향으로만 변하는 문제들이다(그래서 이거만 풀면 나머지 2개는 날로 먹을 수 있다).
E. Xenia and Tree / Äventyr 2

곰곰이 잘 생각해서 d[] 를 만들자.
d[i]: i번 노드가 루트인 subtree에서 i와 가장 가까운 흰색 정점까지의 거리
1번 쿼리면 조상 쫙 돌면서 d[]를 갱신해주면 되고,
2번 쿼리면 조상 쫙 돌면서 v가 조상을 거쳐 흰색 정점으로 가는 min을 구하면 되겠다.

하지만 이렇게만 하면 검은색->흰색이 되는 경우에 문제가 생긴다.
이것은 d[]를 pq<dist, idx>로 만들고 chk[]를 만들어서 d[].top()에 접근하기 전, 빼야 할 걸 다 빼서 해결할 수 있다.

그런데 아주 사소한 문제가 하나 남아있다.
트리의 높이가 n이면 O(n^2)이 되는 아주 사소한 문제...
트리의 높이를 log n 으로 바꾸면 해결되는 아주 사소한 문제다.

여기서 센트로이드 디컴포지션이 쓰인다.
적당히 센트로이드 트리를 구성하고, d[]를 위에서 말한대로 관리하면 잘 풀 수 있다.

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;

int n, q;

vector<int> adj[maxn];
int pa[maxn];
int sz[maxn];
int depth[maxn];
int spar[20][maxn];
bool chk[maxn];
priority_queue<pii, vector<pii>, greater<pii> > dp[maxn];   //x->a  dist

int get_sz(int now, int prev) {
    sz[now] = 1;
    for(auto nxt : adj[now]) if(nxt != prev && pa[nxt] < 0)  sz[now] += get_sz(nxt, now);
    return sz[now];
}

int get_cen(int now, int prev, int cap) {
    for(auto nxt : adj[now])    if(nxt != prev && pa[nxt] < 0 && sz[nxt] > cap) return get_cen(nxt, now, cap);
    return now;
}

void make_cen(int now, int prev) {
    int cap = get_sz(now, -1) / 2;
    int cen = get_cen(now, -1, cap);
    pa[cen] = prev;
    for(auto nxt : adj[cen])    if(pa[nxt] < 0) make_cen(nxt, cen);
}

void make_dep(int now, int prev, int dep) {
    depth[now] = dep;
    for(auto nxt : adj[now])    if(nxt != prev) {
        make_dep(nxt, now, dep + 1);
        spar[0][nxt] = now;
    }
}

int dist(int a, int b) {
    int ret = 0;
    if(depth[a] > depth[b]) swap(a, b);
    for(int i = 19; i >= 0; --i) {
        if(depth[a] <= depth[b] - (1 << i)) {
            ret += 1 << i;
            b = spar[i][b];
        }
    }
    if(a == b)  return ret;
    for(int i = 19; i >= 0; --i) {
        if(spar[i][a] != spar[i][b]) {
            ret += 1 << i + 1;
            a = spar[i][a], b = spar[i][b];
        }
    }
    return ret + 2;
}

void update(int x) {
    int y = x;
    while(y) {
        while(!chk[dp[y].top().se])   dp[y].pop();
        if(chk[x])  dp[y].push({dist(x, y), x});
        y = pa[y];
    }
}

int query(int x) {
    int ret = maxn;
    int y = x;
    while(y) {
        while(!chk[dp[y].top().se])   dp[y].pop();
        ret = min<int>(ret, dp[y].top().fi + dist(x, y));
        y = pa[y];
    }
    return ret;
}

int main(void) {
    chk[0] = true;
    fill(pa, pa + maxn, -1);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) dp[i].push({maxn, 0});
    for(int i = 0; i < n - 1; ++i) {
        int u, v;   scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    make_cen(1, 0);
    make_dep(1, -1, 0);
    for(int b = 1; b < 20; ++b)    for(int i = 1; i <= n; ++i) spar[b][i] = spar[b - 1][spar[b - 1][i]];

    scanf("%d", &q);
    while(q--) {
        int t, u;   scanf("%d%d", &t, &u);
        if(t == 1) {
            chk[u] ^= 1;
            update(u);
        }
        else {
            int ret = query(u);
            printf("%d\n", ret >= maxn ? -1 : ret);
        }
    }
    return 0;
}