记录编号	586577	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.413 s
提交时间	2024-02-07 23:34:14	内存使用	74.70 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e6+10;
int n,m;
struct B{
	int fa[N];
	void clear(){for(int i = 1;i <= n;i++)fa[i] = i;}
	int find(int x){
		if(x == fa[x])return x;
		return fa[x] = find(fa[x]);
	} 
}t;
struct made{
	int ver,nx;
}e[N<<1];
int hd[N],tot;
int fa[N],tim[N],q[N],ans[N];
vector<int>G[N];
void add(int x,int y){
	tot++;
	e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs(int x){
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(y == fa[x])continue;
		fa[y] = x,dfs(y);
	}
}
void merge(int x){
	t.fa[x] = t.find(fa[x]);
}
int main(){
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i < n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1);fa[1] = 1;
	for(int i = 1;i <= m;i++){
		char c[2];int x;
		scanf("%s%d",c,&x);
		if(c[0] == 'Q')q[i] = x;
		else if(!tim[x])tim[x] = i;
	}
	t.clear();
	for(int i = 1;i <= n;i++)G[tim[i]].push_back(i);
	for(int i = 0;i < G[0].size();i++)merge(G[0][i]);
	for(int i = m;i >= 1;i--){
		if(q[i])ans[i] = t.find(q[i]);
		else{
			for(int j = 0;j < G[i].size();j++)merge(G[i][j]);
		}
	}
	for(int i = 1;i <= m;i++)
	    if(q[i])printf("%d\n",ans[i]);
	
	return 0;
	
}