记录编号	370896	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.323 s
提交时间	2017-02-14 19:21:16	内存使用	16.31 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long 
int read(){
	int 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-48,ch=getchar();
	return x*f;
}
const int maxn=1010000;
struct edge{int to,next;}e[maxn*2];
int tot,head[maxn];
void add(int u,int v){
	e[++tot]=(edge){v,head[u]};head[u]=tot;
}
int n,m,black[maxn],q[maxn],ans[maxn];
int fa[maxn],f[maxn];
char op[maxn][2];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int u,int Fa){
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(to==Fa) continue;
		fa[to]=f[to]=find(fa[u]);
		if(black[to]) fa[to]=to;
		dfs(to,u);
	}
}
int main(){
	int __size__=80<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("heoi2016_tree.in","r",stdin);freopen("heoi2016_tree.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<n;i++){
		int a=read(),b=read();
		add(a,b);add(b,a);
	}
	black[1]=1;fa[1]=1;
	for(int i=1;i<=m;i++){
		scanf("%s%d",op[i],&q[i]);
		if(op[i][0]=='C')black[q[i]]++;
	}
	dfs(1,0);
	for(int i=m;i>=1;i--){
		if(op[i][0]=='C'){
			black[q[i]]--;
			if(black[q[i]]) continue;
			else fa[q[i]]=find(f[q[i]]);
		}
		else ans[i]=find(q[i]);
	}
	for(int i=1;i<=m;i++)
		if(op[i][0]=='Q')printf("%d\n",ans[i]);
	fclose(stdin);fclose(stdout);
	return 0;
}