Description:
你拥有一棵有 N 个结点白色的树——所有节点都是白色的。
接下来,你需要处理 C 条指令:
1.修改指令:改变一个给定结点的颜色(白变黑,黑变白);
2.查询指令:询问从结点 1 到一个给定结点的路径上第一个
黑色结点编号。
数据范围:
$N <= 1000000 , C <= 1000000 $

Solution:
对于每条重链开一个set维护深度最小的黑点及其编号，查询就往上跳，修改直接修改就行

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6+5;
struct ed {
    int to,nxt;
}t[mxn<<1];
int n,m,tot,cnt,col[mxn],sz[mxn],hd[mxn],dep[mxn],f[mxn],top[mxn],rk[mxn],id[mxn],son[mxn];
set<pair<int ,int > > s[mxn];

inline void add(int u,int v) {
    t[++cnt]=(ed){v,hd[u]},hd[u]=cnt;
}

void dfs1(int u,int fa)
{
    sz[u]=1; dep[u]=dep[fa]+1; f[u]=fa;
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}

void dfs2(int u,int tp)
{
    top[u]=tp; id[tp]=++tot;
    if(son[u])
    dfs2(son[u],tp);
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(f[u]==v||v==son[u]) continue ;
        dfs2(v,v);
    }
}

int main()
{
    //freopen("Black-White_Tree.in","r",stdin);
    //freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m); int u,v;
    for(int i=1;i<n;++i) {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,0); dfs2(1,0); 
    int opt,x;
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&opt,&x);
        if(opt==0) {
            if(!col[x]) col[x]=1,s[top[x]].insert(make_pair(dep[x],x));
            else col[x]=0,s[top[x]].erase(make_pair(dep[x],x));
        }
        else {
            pair<int ,int > ans; 
            while(x) {
                if(s[top[x]].begin()!=s[top[x]].end())
                    if((*s[top[x]].begin()).first<=dep[x])
                    ans=make_pair((*s[top[x]].begin()).first,(*s[top[x]].begin()).second);
                x=f[top[x]];    
            }
            if(ans.second==0) puts("-1");
            else printf("%d\n",ans.second);
        }
    }

    return 0;
}