记录编号	269404	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]简单的最近公共祖先	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	4.585 s
提交时间	2016-06-13 16:28:06	内存使用	114.73 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 2000010;
struct Edge{
	int to,next;
	Edge(){to=next=0;}
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){
	G[++cnt].to=v;
	G[cnt].next=head[u];
	head[u]=cnt;
}
struct line{
	int flag,u,top;
	bool is_up;
	line(){
		is_up = false;
	}
}lne[maxn];
int deep[maxn],siz[maxn],fa[maxn],map[maxn],son[maxn],top[maxn];
void dfs(int u){
	siz[u] = 1;
	for(int i=head[u];i;i=G[i].next){
		if( G[i].to == fa[u] ) continue;
		int v = G[i].to;
		fa[v] = u;
		deep[v] = deep[u] + 1;
		dfs(v);
		siz[u] += siz[v];
		if( siz[son[u]] < siz[v] )
			son[u] = v;
	}
}
int tim;
void dfs(int u,int tp){
	if(u==tp){
		lne[++tim].top=u;
		map[u]=tim;
	}else map[u] = map[tp];
	top[u]=tp;
	if(son[u]) dfs(son[u],tp);
	for(int i=head[u];i;i=G[i].next){
		int v = G[i].to;
		if( son[u]==v || fa[u]==v )continue;
		dfs(v,v);
	}
}
int n,m,upsum=1;
void update(int u){
	while(u){
		int tmp = map[u];
		if(lne[tmp].flag != upsum){
			lne[tmp].u = lne[tmp].top;
			lne[tmp].flag = upsum;
			lne[tmp].is_up = false;
		}
		lne[tmp].is_up = true;
		if( deep[lne[tmp].u] < deep[u] ) lne[tmp].u=u;
		u = fa[ top[u] ];
	}
}
int Query(int u){
	while(u){
		int tmp = map[u];
		if(lne[tmp].flag == upsum){
			if( lne[tmp].is_up ){
				if(deep[lne[tmp].u] <= deep[u]) return lne[tmp].u;
				else return u;
			}
 
		}
		u=fa[top[u]];
	}
	return -1;
}
int main(){
    int __size__=128<<20;
    char *__p__=(char*)malloc(__size__)+__size__;
    __asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("get_tree.in","r",stdin);
	freopen("get_tree.out","w",stdout);
	read(n),read(m);
	int u,v;
	for(int i=1;i<n;i++){
		read(u),read(v);
		add(u,v);add(v,u);
	}
	deep[1] = 1;
	dfs(1);
	dfs(1,1);
	int x;char ch;
	for(int i=1;i<=m;i++){
		while(ch=getchar(),ch<'!');
		if(ch=='C') ++upsum;
		else if(ch=='M') read(x),update(x);
		else if(ch=='Q') read(x),printf("%d\n",Query(x));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}