外话：最近洛谷加了好多好题啊...原题入口 这题好像是SPOJ的题，挺不错的。看没有题解还是来一篇...

题意

很易懂吧。。

题解

我的做法十分的暴力：树链剖分（伪）+线段树+ std :: set ...

首先，我们可以考虑每次修改一个点的颜色的影响。

易知，翻转一个点颜色，只会对于他的子树产生影响，对于别的点就毫无意义了。

然后，只要学过一点树链剖分的就知道，我们可以将整棵树按它的\(dfs\)序进行标号，

每个点的序号就是\(dfn\)，

然后记下它的子树大小\(size\)，然后对于每个点\(u\)所在的子树区间就是\([dfn[u], dfn[u]+size[u]-1]\)。

所以每次操作的时候，只要对于那一段区间进行修改就行了。

然后我们要修改和查询什么呢？不就是查询包含这个点，且深度最小的黑点吗？（需要把\(1\)作为根）

所以，我们每次记下一个区间中，包含这个点的所有黑色标号以及他们的深度，用\(pair\)记录一下（因为这个可以

自动按照第一关键字排序），再用\(set\)维护一下区间最值就行了。

每次更新的时候只要在\(set\)里面\(insert\)和\(erase\)。

查询就是从根节点一直向下跑，不断取一个深度更小的\(ans\)。

具体有些实现在程序中会体现的……

总时间复杂度\(O(q \log \ n \log q)\) 空间复杂度也是\(O(q \log \ n \log \ q)\)。（所以说很暴力嘛……）

代码

#include <bits/stdc++.h>

#define For(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)

#define Fordown(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');

    return x * fh;

}

void File() {

#ifdef zjp_shadow

    freopen ("P4116.in", "r", stdin);

    freopen ("P4116.out", "w", stdout);

#endif

}

const int N = 1e5 + 1e3, M = N << 1;

int n, q;

int sz[N], dfn[N], dep[N];

int to[M], Next[M], Head[N], e = 0;

void add(int u, int v) {

    to[++e] = v;

    Next[e] = Head[u];

    Head[u] = e;

}

void Dfs(int u, int fa) {

    static int clk = 0;

    sz[u] = 1;

    dfn[u] = ++ clk;

    dep[u] = dep[fa] + 1;

    for (register int i = Head[u]; i; i = Next[i]) {

        register int v = to[i];

        if (v == fa) continue ;

        Dfs(v, u); sz[u] += sz[v];

    }

}//就是树链剖分的第一个dfs,求出size,dep,dfn 

typedef pair<int, int> PII;

#define mp make_pair

#define lson o << 1, l, mid

#define rson o << 1 | 1, mid + 1, r

set<PII> S[N << 2];

bool col[N];//因为不知道是变啥颜色,所以要记一下原来的颜色

bool uopt; int ul, ur; PII uv;

void Update(int o, int l, int r) {

    if (ul <= l && r <= ur) {

        if (uopt) S[o].erase(uv);

        else S[o].insert(uv);

        //erase可以直接调用那个值.

        return ;

    }

    int mid = (l + r) >> 1;

    if (ul <= mid) Update(lson);

    if (ur > mid) Update(rson);

}

PII ans; int up;

void Query(int o, int l, int r) {

    if ((bool)S[o].size() )

        ans = min(ans, *S[o].begin() );

    //begin就是这个set中最小的那一个,即这里面深度最小的那个点

    if (l == r) return ;

    int mid = (l + r) >> 1;

    if (up <= mid) Query(lson);

    else Query(rson);

}

const int inf = 0x3f3f3f3f;

int main () {

    n = read(); q = read();

    For (i, 1, n - 1) {

        int u, v;

        scanf ("%d%d", &u, &v);

        //int u = read(), v = read();

        add(u, v); add(v, u);

    }

    Dfs(1, 0);

    For (i, 1, q) {

        int opt, pos;

        scanf ("%d%d", &opt, &pos);

        //int opt = read(), pos = read();

        if (opt == 0) {

            uopt = col[pos];

            col[pos] ^= true;

            ul = dfn[pos];

            ur = dfn[pos] + sz[pos] - 1;

            uv = mp(dep[pos], pos);

            Update(1, 1, n);

        } else {

            ans = mp(inf, inf);

            up = dfn[pos];

            Query(1, 1, n);

            printf ("%d\n", ans.second == inf ? -1 : ans.second);

        }

    }

    //cerr << clock() << endl;

    return 0;

}

后记：看到很多dalao都是用啥 主席树，倍增，和不用\(set\)的线段树做过去的。跑得都比我快，希望后面有人能讲一讲QAQ。