记录编号	491363	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	HtBest	是否通过	通过
代码语言	C++	运行时间	0.331 s
提交时间	2018-03-16 19:15:09	内存使用	0.97 MiB

#define _CRT_SECURE_NO_DEPRECATE
/************************
*创建时间：2018 03 16
*文件类型：源代码文件
*题目来源：COGS
*采用算法：并查集
*作者：HtBest
 ************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n,q,a[100001],flag[100001];
/* Variable explain:
n:节点个数
q:询问次数
a:并查集
flag:C操作打标记
*/
int find(int x)	{while(flag[x]!=1)x=a[x];	return x;}
int main()
{
	freopen("heoi2016_tree.in","r",stdin);
	freopen("heoi2016_tree.out","w",stdout);
	scanf("%d%d",&n,&q);
	int ls1,ls2;
	char c;
	for(int i=1;i<n;++i)	scanf("%d%d",&ls1,&ls2),a[ls2]=ls1;
	flag[1]=true;
	while(q--)
	{
		scanf("%s%d",&c,&ls1);
		if(c=='C')flag[ls1]=1;
		else	printf("%d\n",find(ls1));
	}
	return 0;
}