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

#include<cstdio>
#include<cstring>
using namespace std;
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;
int main(){
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;i++){
		prt[i]=i;
		sym[i]=false;
	}
	for(i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		prt[v]=u;
	}
	for(i=1;i<=m;i++){
		do oper[i]=getchar();while(oper[i]!='C'&&oper[i]!='Q');
		scanf("%d",&num[i]);
		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]){
		printf("%d\n",result[i]);
	}
	return 0;
}
int b[maxn],k;
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];
}