记录编号	294412	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	6.904 s
提交时间	2016-08-12 06:23:55	内存使用	37.45 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000100;
int N,Q,len=0;
int head[maxn];
struct node
{
	int to,next;
}e[maxn*2];
int Ans[maxn];
void ADD(int x,int y)
{
	len++;
	e[len].to=y;
	e[len].next=head[x];
	head[x]=len;
}
struct NODE
{
	bool op;
	int x;
}A[maxn];
int fa[maxn];
int flag[maxn];
//0是标记 1 是询问 
bool vis[maxn];
void DFS(int x)
{
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next)
	{
		int t=e[i].to;
		if(!vis[t])
		{
			fa[t]=x;
			DFS(t);
		}
	}
}
int Find(int x)
{
	
	if(flag[x]) return x;
	int fx=x,tt;
	while(!flag[fa[fx]])
	{
		fx=fa[fx];//puts("OK");
	}
	while(!flag[fa[x]])
	{
		tt=fa[x],fa[x]=fx,x=tt;
	}
	return fa[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__));*/
	scanf("%d%d",&N,&Q);
	for(int x,y,i=1;i<N;i++)
	{
		scanf("%d%d",&x,&y);
		//ADD(x,y);
		fa[y]=x;
	}
	char ch;
	fa[1]=1;
	//DFS(1);
	//for(int i=1;i<=N;i++)printf("%d\n",fa[i]);
	flag[1]++;
	for(int i=1;i<=Q;i++)
	{
		scanf(" %c%d",&ch,&A[i].x);
		if(ch=='C')
		{
			A[i].op=0;
			flag[A[i].x]++;		
		}
		if(ch=='Q')
		{
			A[i].op=1;
		}
	}
	
	int Len=0;
	for(int i=Q;i>=1;i--)
	{
		if(A[i].op==0)
		{
			flag[A[i].x]--;continue;
		}
		else
		{
			Len++;
			Ans[Len]=Find(A[i].x);
		}
	}
	for(int i=Len;i>=1;i--)
	{
		printf("%d\n",Ans[i]);
	}
	fclose(stdin);
	fclose(stdout);
 	return 0;
}