记录编号	268011	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	6.707 s
提交时间	2016-06-11 20:04:45	内存使用	58.47 MiB

#define lson l,mid,t
#define rson mid+1,r,t|1

#define maxn 1000010ul

#include <stdio.h>
#include <algorithm>

struct Edge{int v,nx;}edge[maxn<<1];
int n,q,ec,upv,posl,posr,pos,dfs_clock,son[maxn],dfn[maxn],fa[maxn],siz[maxn],depth[maxn],headlist[maxn],top[maxn],tree[maxn<<2];
bool tag[maxn]; char op;

void add_edge(int u,int v){
	edge[++ec]=(Edge){v,headlist[u]};
	headlist[u]=ec;
	return;
}

void dfs1(int x){
	siz[x]=1;
	for(int i=headlist[x];i;i=edge[i].nx) if(edge[i].v!=fa[x]){
		fa[edge[i].v]=x;
		depth[edge[i].v]=depth[x]+1;
		dfs1(edge[i].v);
		siz[x]+=siz[edge[i].v];
		if(siz[edge[i].v]>siz[son[x]]) son[x]=edge[i].v;
	}
	return;
}

void dfs2(int x,int tp){
	top[x]=tp,dfn[x]=++dfs_clock;
	if(son[x]) dfs2(son[x],tp);
	for(int i=headlist[x];i;i=edge[i].nx){
		if(edge[i].v==fa[x]||edge[i].v==son[x]) continue;
		dfs2(edge[i].v,edge[i].v);
	}
	return;
}

void modify(int l,int r,int rt){
	if(l==r){tree[rt]=upv;return;}
	int mid=(l+r)>>1,t=rt<<1;
	if(pos<=mid) modify(lson);
	else modify(rson);
	if(tree[t|1]) tree[rt]=tree[t|1];
	else tree[rt]=tree[t];
	return;
}

int query(int l,int r,int rt){
	if(posl<=l&&posr>=r) return tree[rt];
	int mid=(l+r)>>1,t=rt<<1,t1=0,t2=0;
	if(posl<=mid) t1=query(lson);
	if(posr>mid) t2=query(rson);
	return t2?t2:t1;
}

void read(int &x){
	x=0; int c=getchar(); for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); return;
}

int main(){
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	int __size__=64<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	read(n),read(q);
	for(int i=1,x,y;i<n;i++){
		read(x),read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	depth[1]=1;
	dfs1(1),dfs2(1,1);
	tag[1]=true,pos=dfn[1],upv=1,modify(1,n,1);
	for(int i=1,x;i<=q;i++){
		op=getchar(); while(op!='Q'&&op!='C') op=getchar(); read(x);
		if(op=='C'){
			if(tag[x]) continue;
			tag[x]=true;
			pos=dfn[x],upv=x;
			modify(1,n,1);
		}
		else{
			int ret=0;
			while(top[x]!=1&&!ret){
				posl=dfn[top[x]],posr=dfn[x];
				ret=query(1,n,1);
				x=fa[top[x]];
			}
			if(!ret){
				posl=dfn[1],posr=dfn[x];
				ret=query(1,n,1);
			}
			printf("%d\n",ret);
		}
	}
	return 0;
}