记录编号	309408	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	7.965 s
提交时间	2016-09-19 17:10:55	内存使用	40.16 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N=1000010;
int cnt,fir[N],to[N*2],nxt[N*2];
void addedge(int a,int b){
	nxt[++cnt]=fir[a];
	to[fir[a]=cnt]=b;
}
int fa[N],vis[N],pre[N];
int qr[N],tp[N],ans[N];
void DFS(int x){
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=pre[x]){
			pre[to[i]]=x;
			DFS(to[i]);
		}
}
void DFS(int x,int f){
	fa[x]=f;
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=pre[x]){
			if(!vis[to[i]])DFS(to[i],f);
			else DFS(to[i],to[i]);
		}
}
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
int n,Q;char op[5];
int main(){
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	int sz=32<<20;
	char*p=(char*)malloc(sz)+sz;
	__asm__("movl %0,%%esp\n"::"r"(p));
	scanf("%d%d",&n,&Q);
	for(int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}DFS(1);
	for(int i=1;i<=Q;i++){
		scanf("%s%d",op,&qr[i]);
		tp[i]=op[0]=='Q'?0:1;
	}
	vis[1]=1;
	for(int i=1;i<=Q;i++)
		if(tp[i])vis[qr[i]]+=1;
	DFS(1,1);
	for(int i=Q;i>=1;i--){
		if(!tp[i])
			ans[i]=Find(qr[i]);
		else{
			if(!--vis[qr[i]]){
				int x=qr[i];
				fa[x]=Find(pre[x]);
			}
		}
	}
	for(int i=1;i<=Q;i++)
		if(!tp[i])printf("%d\n",ans[i]);
	return 0;
}