记录编号	593880	评测结果	AAAAA
题目名称	[HZOI 2015]白黑树	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2024-09-20 18:54:05	内存使用	13.09 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,m,tot,h[200010],ne[400010],v[400010];
int a[400010],b[200010][2],w[200010],f[200010][25],t,s,vi[200010];
queue<int> q;
void add(int x,int y)
{
    tot++;
    v[tot]=y;
    ne[tot]=h[x];
    h[x]=tot;
}
void dfs(int x,int fa)
{
    tot++;
    b[x][0]=tot;
    for(int i=h[x];i;i=ne[i])
    {
        int y=v[i];
        if(y==fa) continue;
        f[y][0]=x;
        dfs(y,x);
    }
    tot++;
    b[x][1]=tot;
}
void bfs()
{
    q.push(1);
    v[1]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=ne[i])
        {
            int y=v[i];
            if(vi[y]) continue;
            vi[y]=1;
            for(int j=1;j<=t;j++)
            {
                f[y][j]=f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}
void work(int x,int y)
{
    for(;x<=2*n;x+=x&-x) a[x]+=y;
}
int ask(int x)
{
    int sum=0;
    for(;x;x-=x&-x) sum+=a[x];
    return sum;
}
int qu(int x)
{
    if(ask(b[x][1])-ask(b[x][0]-1)==s) return x;
    for(int i=t;i>=0;i--)
    {
        int fa=f[x][i];
        if(fa==0||b[fa][0]==0) continue;
        if(ask(b[fa][1])-ask(b[fa][0]-1)<s) x=fa;
    }
    return f[x][0];
}
int main()
{
    freopen("C_Tree.in","r",stdin);
    freopen("C_Tree.out","w",stdout);
    scanf("%d%d",&n,&m);
    t=(int)(log(n)/log(2))+1;
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u); 
    }
    tot=0;
    dfs(1,0);
    bfs();
    for(int i=1;i<=m;i++)
    {
        char p;
        scanf(" %c",&p);
        if(p=='M')
        {
            int u;
            scanf("%d",&u);
            if(w[u]==0)
            {
                work(b[u][0],1);
                w[u]=1;
                s++;
            } 
            else
            {
                work(b[u][0],-1);
                w[u]=0;
                s--;
            }
        }
        else
        {
            int u;
            scanf("%d",&u);
            if(s==0) printf("-1\n");
            else printf("%d\n",qu(u));
        }
    }
    return 0;
}