原题P4092

TLE#11,92分求条

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,fa[100005],v[100005];
int getfa(int x){
	if(v[x]==1||x==1)return x;
	else return getfa(fa[x]);
}
signed main(){
	cin>>n>>m;
	fa[1]=1;
	v[1]=1;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		fa[y]=x;
	}
	for(int i=1;i<=m;i++){
		char o;
		int x;
		cin>>o>>x;
		if(o=='C'){
			v[x]=1;
		}
		else if(o=='Q'){
			cout<<getfa(x)<<endl;
		}
	}
	return 0;
}