记录编号	265273	评测结果	EEEEEEEEEE
题目名称	[HZOI 2015]简单的最近公共祖先	最终得分	0
用户昵称	hebomou	是否通过	未通过
代码语言	C++	运行时间	8.472 s
提交时间	2016-06-02 12:15:00	内存使用	94.70 MiB

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <cstdio>
#include <climits>

using namespace std;

const int MAXN=2000005;

int N,M;

namespace Dec{
	struct Edge{
		int to,next;
	}E[MAXN*2];int EL;
	int Head[MAXN];
	struct Node{
		int siz,chr,dep,f;
		int top,id;
	}A[MAXN];
	int Mx[MAXN];
	set<int> Black;
	void Add_Edge(int a,int b){
		E[++EL].to=b;
		E[EL].next=Head[a];
		Head[a]=EL;
		E[++EL].to=a;
		E[EL].next=Head[b];
		Head[b]=EL;
	}
	void DFS1(int p){
		A[p].dep=A[A[p].f].dep+1;
		A[p].siz=1;
		for(int i=Head[p];i;i=E[i].next){
			int to=E[i].to;
			if(A[to].dep)continue;
			A[to].f=p;
			DFS1(to);
			A[p].siz+=A[to].siz;
			if(A[to].siz>A[A[p].chr].siz)
				A[p].chr=to;
		}
	}
	int DFN;
	void DFS2(int p,int top){
		A[p].id=++DFN;
		A[p].top=top;
		if(A[p].chr){
			DFS2(A[p].chr,top);
			for(int i=Head[p];i;i=E[i].next){
				int to=E[i].to;
				if(A[to].id)continue;
				DFS2(to,to);
			}
		}
	}
	void Build(){
		DFS1(1);
		DFS2(1,1);
	}
	void Clear(){
		for(set<int>::iterator it=Black.begin();it!=Black.end();it++){
			Mx[*it]=0;
		}
		Black.clear();
	}
	void Mark(int a){
		while(a){
			Black.insert(A[a].top);
			if(A[a].dep>A[Mx[A[a].top]].dep)
				Mx[A[a].top]=a;
			a=A[A[a].top].f;
		}
	}
	void Get(int a){
		while(a){
			int mx=Mx[A[a].top];
			if(mx){
				if(A[mx].dep>A[a].dep)
					printf("%d\n",a);
				else printf("%d\n",mx);
				return;
			}
			a=A[A[a].top].f;
		}
		puts("-1");
	}
};

int main(){
	int __size__=70<<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);
	scanf("%d%d",&N,&M);
	for(int i=1;i<N;i++){
		int a,b;scanf("%d%d",&a,&b);
		Dec::Add_Edge(a,b);
	}
	Dec::Build();
	while(M--){
		char str[10];int a;
		scanf("%s",str);
		if(str[0]=='C')
			Dec::Clear();
		else{
			scanf("%d",&a);
			if(str[0]=='M')
				Dec::Mark(a);
			if(str[0]=='Q')
				Dec::Get(a);
		}
	}
	return 0;
}