记录编号	254563	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2016-04-25 15:04:25	内存使用	0.81 MiB

#include<cstdio>
#include<cstring>
using namespace std;
namespace mine{
	int c,x,a[110],i,j;
	bool neg;
	inline int getint(){
		x=neg=0;
		do c=getchar();while(c==' '||c=='\n'||c=='\r'||c=='\t');
		if(c=='-'){
			neg=true;
			c=getchar();
		}
		for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
		if(neg)return -x;
		return x;
	}
	inline int fgeti(FILE* fin){
		x=neg=0;
		do c=fgetc(fin);while(c==' '||c=='\n'||c=='\r'||c=='\t');
		if(c=='-'){
			neg=true;
			c=fgetc(fin);
		}
		for(;c>='0'&&c<='9';c=fgetc(fin))x=(x<<1)+(x<<3)+(c^48);
		if(neg)return -x;
		return x;
	}
	inline void putint(int x){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)putchar(a[j]);
	}
	inline void fputi(FILE* fout,int x){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)fputc(a[j],fout);
	}
	inline void fputi(int x,FILE* fout){
		neg=x<0;
		if(neg)x=-x;
		i=0;
		do{
			a[i++]=x%10+48;
			x/=10;
		}while(x);
		if(neg)putchar('-');
		for(j=i-1;j>=0;j--)fputc(a[j],fout);
	}
	inline void put(const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)putchar(s[i]);
	}
	inline void fput(FILE* fout,const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
	}
	inline void fput(const char* s,FILE* fout){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
	}
	inline void puts(const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)putchar(s[i]);
		putchar('\n');
	}
	inline void fputs(FILE* fout,const char* s){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
		fputc('\n',fout);
	}
	inline void fputs(const char* s,FILE* fout){
		x=strlen(s);
		for(i=0;i<x;i++)fputc(s[i],fout);
		fputc('\n',fout);
	}
}
const int maxn=100010;
int prt[maxn],first[maxn]={0};
bool sym[maxn];
int n,m,u,v;
char oper[maxn];
int num[maxn],result[maxn];
int findroot(int);
int i;
inline int MAIN(){
	freopen("heoi2016_tree.in","r",stdin);
	freopen("heoi2016_tree.out","w",stdout);
	n=mine::getint();
	m=mine::getint();
	for(i=0;i<=n;i++){
		prt[i]=i;
		sym[i]=false;
	}
	for(i=1;i<n;i++){
		u=mine::getint();
		v=mine::getint();
		prt[v]=u;
	}
	for(i=1;i<=m;i++){
		do oper[i]=getchar();while(oper[i]!='C'&&oper[i]!='Q');
		num[i]=mine::getint();
		if(oper[i]=='C'){
			if(first[num[i]]==0)first[num[i]]=i;
			sym[num[i]]=true;
		}
	}
	sym[1]=true;
	first[1]=-1;
	for(i=m;i;i--){
		if(oper[i]=='C'){
			if(i==first[num[i]])sym[num[i]]=false;
			result[i]=0;
		}
		else result[i]=findroot(num[i]);
	}
	for(i=1;i<=m;i++)if(result[i]){
		mine::putint(result[i]);
		putchar('\n');
	}
	return 0;
}
int haha=MAIN();
int main(){;}
/*inline int findroot(int x){
	if(sym[x])return x;
	if(prt[x]!=x)prt[x]=findroot(prt[x]);
	return prt[x];
}*/
int b[maxn],k;
inline int findroot(int x){
	if(sym[x])return x;
	k=0;
	int j;
	for(j=x;prt[j]!=j&&!sym[j];j=prt[j])b[k++]=j;
	if(sym[j])b[k++]=j;
	for(int i=0;i<k-1;i++)prt[b[i]]=b[k-1];
	return prt[x];
}
//一个findroot都写不对,剁手剁手!!!!!!