记录编号	443568	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	Letter zZZz	是否通过	通过
代码语言	C++	运行时间	0.720 s
提交时间	2017-08-31 15:11:50	内存使用	0.96 MiB

#include <fstream>
#include <iostream>
using namespace std;
ifstream fi ("heoi2016_tree.in");
ofstream fo ("heoi2016_tree.out");
int main()
{
	int N,Q,u,v,i,num,k;
	int tree[100001]={0},sig[100001]={0};
	string L;
	sig[1]=1;
	fi>>N>>Q;
	for (i=1;i<=N-1;i++)
	{
		fi>>u>>v;
		tree[v]=u;
	}
	for (int j=1;j<=Q;j++)
	{
		fi>>L>>num;
		if (L=="C")
			sig[num]=1;
		else if (L=="Q")
		{
			k=num;
			int t=0;
			do
			{
				if (sig[k]==1)
				{
					fo<<k<<endl;
					t=1;
				}
				else if (sig[tree[k]]==1)
				{
					fo<<tree[k]<<endl;
					t=1;
				}
				else k=tree[k];
			}while (t==0);
		}
	}
	return 0;
}