记录编号	309361	评测结果	EEEEEEEEEE
题目名称	[HEOI 2016] 树	最终得分	0
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	1.771 s
提交时间	2016-09-19 16:15:27	内存使用	80.42 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N=1000010;
int cnt,fir[N],nxt[N*2],to[N*2];
void addedge(int a,int b){
	nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;
	nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;
}
int sz[N],son[N],fa[N],dep[N];
void DFS(int x){sz[x]=1;
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x]){
			dep[to[i]]=dep[fa[to[i]]=x]+1;
			DFS(to[i]);sz[x]+=sz[to[i]];
			if(sz[son[x]]<sz[to[i]])son[x]=to[i];
		}
}
int tot,id[N],rid[N],top[N];
void DFS(int x,int tp){
	top[rid[id[x]=++tot]=x]=tp;
	if(son[x])DFS(son[x],tp);
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x]&&to[i]!=son[x])
			DFS(to[i],to[i]);
}
int sum[N*4],pos[N*4];
#define mid (l+r>>1)
void Push_up(int x){
	sum[x]=sum[x<<1]+sum[x<<1|1];
	if(sum[x]==0)pos[x]=0;
	if(sum[x<<1|1])pos[x]=pos[x<<1|1];
	else pos[x]=pos[x<<1];
}
void Update(int x,int l,int r,int g){
	if(l==r){pos[x]=rid[l];sum[x]+=1;return;}
	if(mid>=g)Update(x<<1,l,mid,g);
	else Update(x<<1|1,mid+1,r,g);
	Push_up(x);
}

int Query(int x,int l,int r,int a,int b){
	//if(!sum[x])return 0;
	if(l>=a&&r<=b)return pos[x];int ret=0;
	if(mid<b)ret=Query(x<<1|1,mid+1,r,a,b);
	if(!ret&&mid>=a)ret=Query(x<<1,l,mid,a,b);
	return ret;	
}

int tag[N],n,Q,x;
int Solve(int x){
	while(x){
		int d=Query(1,1,n,id[top[x]],id[x]);
		if(d)return d;x=fa[top[x]];
	}
	return 0;
}
char op[5];
int main(){
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	int size = 32 << 20; // 256MB  
	char *p = (char*)malloc(size) + size;  
	__asm__("movl %0, %%esp\n" :: "r"(p)); 
	scanf("%d%d",&n,&Q);
	for(int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
	}
	DFS(1);DFS(1,1);
	Update(1,1,n,1);tag[1]=1;
	while(Q--){
		scanf("%s%d",op,&x);
		if(op[0]=='C'){
			if(tag[x])continue;
			Update(1,1,n,id[x]);
			tag[x]=1;
		}
		else{
			printf("%d\n",Solve(x));
		}
	}
	return 0;
}