spoj QTREE3(树剖+线段树)

spoj QTREE3
树剖，然后线段树维护区间第一个出现的黑点。由于单点修改所以很简单了
(注意！树剖的$u,p_u,np_u$的意义要弄清楚！树剖时重点检查对象)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5, INF = 1000000000;
int n, Q;
vector<int> G[MAXN];
void ins(int u, int v) {
    G[u].push_back(v), G[v].push_back(u);
}
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN], p[MAXN], np[MAXN], top[MAXN], tb;
void dfs1(int u, int p) {
    fa[u] = p, siz[u] = 1, dep[u] = dep[p] + 1;
    for (int i = 0;i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (v != p) {
            dfs1(v, u);
            siz[u] += siz[v];
            if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
        }
    }
}
void dfs2(int u, int chain) {
    p[u] = ++tb;
    np[p[u]] = u;
    top[u] = chain;
    if (son[u] != -1) {
        dfs2(son[u], chain);
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            if (v != son[u] && v != fa[u]) {
                dfs2(v, v);
            }
        }
    }
}
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
int col[MAXN * 4], tag[MAXN * 4];
void pushup(int o) {
    tag[o] = min(tag[lc], tag[rc]);
}
void update(int o, int l, int r, int x) {
    if (l == r) {
        col[o] = !col[o];
        if (col[o] == 1) tag[o] = l;
            else tag[o] = INF;
        return ;
    }
    if (x <= M) update(lc, l, M, x);
    else if (M < x) update(rc, M + 1, r, x);
    pushup(o);
}
int query(int o, int l, int r, int x, int y) {
    int ret = INF;
    if (x <= l && r <= y) {
        return tag[o];
    }
    if (x <= M) ret = min(ret, query(lc, l, M, x, y));
    if (M < y) ret = min(ret, query(rc, M + 1, r, x, y));
    return ret;
}
int find(int u, int v) {
    int f1 = top[u], f2 = top[v], ret = INF;
    while (f1 != f2) {
        if (dep[f1] < dep[f2]) swap(u, v), swap(f1, f2);
        ret = min(ret, query(1, 1, n, p[f1], p[u]));
        u = fa[f1], f1 = top[u];
    }
    if (dep[u] < dep[v]) swap(u, v);
    return min(ret, query(1, 1, n, p[v], p[u]));
}
void clean() {
    tb = 0;
    for (int i = 0; i <= 4 * n; i++) col[i] = 0, tag[i] = INF;
    for (int i = 0; i <= n; i++) {
        G[i].clear(), np[i] = p[i] = top[i] = fa[i] = dep[i] = 0, son[i] = -1;
    }
}
void solve() {
    clean();
    for (int u, v, i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        ins(u, v);
    }
    dfs1(1, 0), dfs2(1, 1);
    while (Q--) {
        int opt, a;
        scanf("%d%d", &opt, &a);
        if (opt == 0) {
            update(1, 1, n, p[a]);
        } else {
            int ans = find(1, a);
            printf("%d\n", ans == INF ? -1 : np[ans]); 
        }
    }
}
int main() { 
    //freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); 
    scanf("%d%d", &n, &Q), solve();
    return 0;
}