记录编号	267962	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	35.277 s
提交时间	2016-06-11 19:39:33	内存使用	51.01 MiB

#include<cstdio>
#include<cstdlib>
 
#define maxn 1000010
 
using namespace std;
 
int n,m,dfn[maxn],son[maxn],num,inv[maxn],top[maxn],fa[maxn],tr[maxn<<2];
int tot,b[maxn],siz[maxn];
char C[10];
 
int read()
{
	int ret=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret; 
}
 
struct edge{
	int x,y,last;
}a[maxn];
 
void add(int x,int y)
{
	a[++tot]=(edge){x,y,b[x]};
	b[x]=tot;
}
 
void dfs1(int x)
{
	siz[x]=1;
	for(int i=b[x];i;i=a[i].last){
		int v=a[i].y;
		fa[v]=x;
		dfs1(v);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]]) son[x]=v;
	}
}
 
void dfs2(int x)
{
	dfn[x]=++num;inv[num]=x;
	if(son[x]) top[son[x]]=top[x],dfs2(son[x]);
	else return;
	for(int i=b[x];i;i=a[i].last){
		int v=a[i].y;
		if(v!=son[x]) top[v]=v,dfs2(v);
	}
}
 
void update(int x)
{
	tr[x]=tr[x<<1]+tr[x<<1|1];
}
 
void modify(int pos,int l,int r,int x)
{
	if(l==r){
		tr[x]=1;
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid) modify(pos,l,mid,x<<1);
	else modify(pos,mid+1,r,x<<1|1);
	update(x);
	return;
}
 
int query(int al,int ar,int l,int r,int x)
{
	if(al<=l&&r<=ar) return tr[x];
	int mid=l+r>>1,ret=0;
	if(al<=mid) ret=query(al,ar,l,mid,x<<1);
	if(ar>mid) ret+=query(al,ar,mid+1,r,x<<1|1);
	return ret;
}
 
int work(int l,int r)
{
	int ans=0;
	while(l<=r){
		int mid=l+r>>1;
		if(query(mid,r,1,n,1)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return inv[ans];
}
 
int solve(int x)
{
	while(x){
		int s=query(dfn[top[x]],dfn[x],1,n,1);
		if(s){
			return work(dfn[top[x]],dfn[x]);
		}
		x=fa[top[x]];
	}
	return 1;
}
 
int main()
{
	int __size__ = 50 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		add(x,y);
	}
	dfs1(1);
	dfs2(1);
	modify(dfn[1],1,n,1);
	for(int i=1;i<=m;i++){
		int x;
		scanf("%s",C);
		x=read();
		if(C[0]=='C'){
			modify(dfn[x],1,n,1);
		}else{
			printf("%d\n",solve(x));
		}
	}
	return 0;
}