记录编号	593787	评测结果	WWWWW
题目名称	[HZOI 2015]白黑树	最终得分	0
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	0.878 s
提交时间	2024-09-13 22:04:29	内存使用	40.54 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200010
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar(); 
    }
    return x*f;
}
struct node{
    ll l,r,tag;
}tr[MAXN*4];
ll n,m,idx,cnt,sum_col;
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll fa[MAXN][50],dep[MAXN],son[MAXN],tp[MAXN],siz[MAXN],seat[MAXN],col[MAXN];
void build(ll x,ll y){
    nxt[++idx]=hd[x];
    hd[x]=idx;
    ed[idx]=y;
}
void dfs1(ll now,ll fat){
    fa[now][0]=fat,dep[now]=dep[fat]+1,siz[now]=1;
    for(int i=hd[now];i;i=nxt[i]){
        ll y=ed[i];
        if(y==fat)continue;
        dfs1(y,now);
        siz[now]+=siz[y];
        if(siz[y]>siz[son[now]])son[now]=y;
    }
    for(int i=1;i<=20;i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
}
void dfs2(ll now,ll fnt){
    tp[now]=fnt,seat[now]=++cnt;
    if(!son[now])return;
    dfs2(son[now],fnt);
    for(int i=hd[now];i;i=nxt[i]){
        ll y=ed[i];
        if(y==fa[now][0]||y==son[now])continue;
        dfs2(y,y);
    }
}
void tr_build(ll l,ll r,ll now){
    tr[now].l=l,tr[now].r=r;
    if(l==r)return;
    ll mid=(l+r)/2;
    tr_build(l,mid,now*2);
    tr_build(mid+1,r,now*2+1);
}
void push_down(ll now){
    tr[now*2+1].tag+=tr[now].tag;
    tr[now*2].tag+=tr[now].tag;
    tr[now].tag=0;
}
void ad_tr(ll l,ll r,ll now,ll ad_col){
    if(tr[now].l>=l&&tr[now].r<=r){
        tr[now].tag+=ad_col;
        return;
    }
    push_down(now);
    ll mid=(tr[now].l+tr[now].r)/2;
    if(l<=mid)ad_tr(l,r,now*2,ad_col);
    if(r>mid)ad_tr(l,r,now*2+1,ad_col);
}
ll re_tr(ll p,ll now){
    if(tr[now].l==tr[now].r)return tr[now].tag;
    push_down(now);
    ll mid=(tr[now].l+tr[now].r)/2;
    if(p<=mid)return re_tr(p,now*2);
    else return re_tr(p,now*2+1);
}
void ad_(ll p,ll ad_col){
    while(p){
//        cout<<p<<" "<<tp[p]<<endl;
        ad_tr(seat[tp[p]],seat[p],1,ad_col);
        p=fa[tp[p]][0];
    }
}
ll re_(ll u){
    if(re_tr(seat[u],1)==sum_col)return u;
    ll now=u;
    for(int i=20;i>=0;i--){
        if(fa[now][i]&&re_tr(seat[fa[now][i]],1)<sum_col)now=fa[now][i];
    }
    now=fa[now][0];
    if(!now)return -1;
    else return now;
}
int main(){
    freopen("C_Tree.in","r",stdin);
    freopen("C_Tree.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<n;i++){
        ll x,y;
        x=read(),y=read();
        build(x,y);
        build(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    tr_build(1,n,1);
    for(int i=1;i<=m;i++){
        char ch;
        ll a;
        cin>>ch;
        a=read();
        if(ch=='Q'){
            if(!sum_col)cout<<"-1\n";
            else cout<<re_(a)<<endl;
        }
        else if(col[a]){
            col[a]=0;
            ad_(a,-1);
            sum_col--;
        }else{
            sum_col++;
            col[a]=1;
            ad_(a,1);
        }
    }
    return 0;
}