记录编号	600829	评测结果	AAAAA
题目名称	[HZOI 2015]白黑树	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	0.646 s
提交时间	2025-05-19 16:46:19	内存使用	8.73 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,cnt,head[N],tag[N<<2];
struct tree{
    int val,pos;
}t[N<<2];
struct edge{
    int v,next;
}e[N<<1];
void addedge(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
tree merge(tree x,tree y){
    tree ans;
    if(x.val==y.val) ans.val=x.val,ans.pos=(x.pos>y.pos?x.pos:y.pos);
    else ans=(x.val>y.val)?x:y;
    return ans;
}
void build(int p,int l,int r){
    if(l==r){
        t[p].val=0; t[p].pos=l;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p]=merge(t[p<<1],t[p<<1|1]); 
}
void addtag(int p,int d){
    t[p].val+=d;
    tag[p]+=d;
}
void push_down(int p,int l,int r){
    if(!tag[p]) return;
    addtag(p<<1,tag[p]);
    addtag(p<<1|1,tag[p]);
    tag[p]=0;
}
void update(int p,int l,int r,int L,int R,int d){
    if(L<=l && r<=R){
        addtag(p,d);
        return;
    }
    push_down(p,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,L,R,d);
    if(R>mid) update(p<<1|1,mid+1,r,L,R,d);
    t[p]=merge(t[p<<1],t[p<<1|1]);
}
tree query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R) return t[p];
    push_down(p,l,r);
    int mid=(l+r)>>1;
    tree ans={-1,0};
    if(L<=mid) ans=query(p<<1,l,mid,L,R);
    if(R>mid){
        tree tmp=query(p<<1|1,mid+1,r,L,R);
        ans = (ans.val==-1) ? tmp : merge(ans,tmp);
    }
    return ans;
}
int son[N],deep[N],num,siz[N],dfn[N],fa[N],top[N],k[N];
void dfs1(int u,int f){
    fa[u]=f; deep[u]=deep[f]+1; siz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp){
    dfn[u]=++num; top[u]=tp; k[num]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v!=fa[u] && v!=son[u]) dfs2(v,v);
    }
}
void update_path(int u,int d){
    while(u){
        update(1,1,n,dfn[top[u]],dfn[u],d);
        u=fa[top[u]];
    }
}
tree query_path(int u){
    tree ans={-1,0};
    while(u){
        tree tmp=query(1,1,n,dfn[top[u]],dfn[u]);
        ans = (ans.val==-1) ? tmp : merge(tmp,ans);
        u=fa[top[u]];
    }
    return ans;
}
int co[N],bn;
int main(){
	freopen("C_Tree.in","r",stdin);
	freopen("C_Tree.out","w",stdout); 
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char op; int x;
        scanf(" %c%d",&op,&x);
        if(op=='Q'){
            if(!bn) puts("-1");
            else{
                tree res=query_path(x);
                printf("%d\n",k[res.pos]);
            }
        }else{
            if(co[x]){
                update_path(x,-1);
                bn--;
            }else{
                update_path(x,1);
                bn++;
            }
            co[x]^=1;
        }
    }
    return 0;
}