记录编号	380387	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.142 s
提交时间	2017-03-09 08:54:21	内存使用	1.08 MiB

//\
2274.[HEOI 2016]_tree

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define is_num(tmp) (tmp<='9' and tmp>='0')
inline int in(void){
	char tmp=getchar();
	int res(0),f(1);
	while(!(is_num(tmp)||tmp=='-'))tmp=getchar();
	if(tmp=='-')f=-1,tmp=getchar();
	while(is_num(tmp))
	  res=(res<<1)+(res<<3)+(tmp^48),
	  tmp=getchar();
	return res*f;
}//\
#define LOCAL
#define MAXN 100100
struct NODE{
	bool k;
	int f;
	NODE():k(false),f(-1){;}
}s[MAXN];
inline int Find(int i){
	if(s[i].k)return i;
	while(i!=1&&!s[i].k){
		i=s[i].f;
	}
	return i;
}
int N,Q,arg;
char com[2];
int main(){
#ifndef LOCAL
	freopen("heoi2016_tree.in","r",stdin);
	freopen("heoi2016_tree.out","w",stdout);
#endif
	N=in(),Q=in();
	for(int i=1;i<N;++i){
		int a=in(),b=in();
		s[b].f=a;
	}
	s[1].k=true;
	for(int i=1;i<=Q;++i){
		scanf("%s",com);
		arg=in();
		switch(com[0]){
			case 'Q':{
				printf("%d\n",Find(arg));
				break;
			}
			case 'C':{
				s[arg].k=true;
				break;
			}
		}
	}
	return 0;
}