记录编号	593668	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	AeeE5x	是否通过	通过
代码语言	C++	运行时间	0.646 s
提交时间	2024-09-07 13:27:05	内存使用	3.51 MiB

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
#define rev(x) reverse(x.begin(),x.end())
using namespace std;
int n,q;
int fa[100010];

inline int find(int x){
	if(x==fa[x]) return x;
	return find(fa[x]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("heoi2016_tree.in","r",stdin);
	freopen("heoi2016_tree.out","w",stdout);
	
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		fa[b]=a;
	}
	fa[1]=1;
	
	while(q--){
		char x;cin>>x;
		int p;cin>>p;
		if(x=='Q') cout<<find(p)<<endl;
		else fa[p]=p;
	}
	
	return 0;
}