记录编号	302410	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	Drench	是否通过	通过
代码语言	C++	运行时间	7.552 s
提交时间	2016-09-04 09:45:54	内存使用	18.31 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int father[1000005];
int root[1000005];
char oper[1000005];
int num[1000005];
int tag[1000005];
int ans[1000005];
int findset(int x)
{
	if(father[x]!=x)
		father[x]=findset(father[x]);
	return father[x];
}
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__));
	int n,q;
	scanf("%d %d",&n,&q);
	father[1]=1;tag[1]=1;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		//if(u>v) swap(u,v);
		father[v]=u;
	}	
	for(int i=1;i<=n;i++)
		root[i]=father[i];
	for(int i=q;i>=1;i--)
	{	
		char tmp=getchar();
		while(tmp!='C' && tmp!='Q')
			tmp=getchar();
		oper[i]=tmp;
		scanf("%d",&num[i]);
		if(oper[i]=='C') tag[num[i]]++;
	}
	for(int i=1;i<=n;i++)
		if(tag[i])
			father[i]=i;
	for(int i=1;i<=q;i++)
	{
		if(oper[i]=='Q')
			if(tag[num[i]])
				ans[i]=num[i];
			else
				ans[i]=findset(root[num[i]]);
		else if(oper[i]=='C')
		{
			tag[num[i]]--;
			if(!tag[num[i]]) 
				father[num[i]]=root[num[i]];
		}
	}
	for(int i=q;i>=1;i--)
		if(ans[i])
			printf("%d\n",ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}