记录编号	267873	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2332.[HZOI 2016]tree—增强版	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	3.580 s
提交时间	2016-06-11 18:12:16	内存使用	11.71 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 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]);
	}
}
const int maxn=1001000;
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("tree++.in","r",stdin);
	freopen("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(){;}
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];
}