记录编号	257811	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	1.144 s
提交时间	2016-05-02 19:25:57	内存使用	1.84 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100005;
vector<int> f[maxn];
queue<int> q;
int vis[maxn];
int bfs(int x)
{
	q.push(x);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		if(vis[t]==1)
		{
			return t;
		}
		for(int i=0;i<f[t].size();i++)
		{
			q.push(f[t][i]);
		}
	}
}
int main()
{
	freopen("heoi2016_tree.in","r",stdin);
	freopen("heoi2016_tree.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		f[y].push_back(x);
	}
	vis[1]=1;
	char c;
	for(int i=1;i<=m;i++)
	{
		cin>>c;
		if(c=='Q')
		{
			int z;
			scanf("%d",&z);
			printf("%d\n",bfs(z));
		}
		else
		{
			int w;
			scanf("%d",&w);
			vis[w]=1;
		}
	}
	return 0;
}