记录编号	254655	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.305 s
提交时间	2016-04-25 15:37:02	内存使用	2.32 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
const int maxn = 100000 + 10 ;
struct Edge{
	int next,to;
	Edge(){
		next = 0 ;
	}
}G[maxn];
int head[maxn],cnt=0;
void add(int u,int v){
	G[++cnt].to = v;
	G[cnt].next = head[u];
	head[u] = cnt ;
}
int n,m,d[maxn],nub[maxn]={0};
int q[maxn],l=0,r=0;
void BFS(int s){
	if( nub[s] == s ) return;
	l = r = 0;
	q[r] = s ;d[s] = 0;
	nub[s] = s;
	int cnt = 0;
	while( l<=r ){
		cnt++;
		int t = q[l++];
		for(int i=head[t];i;i=G[i].next){
			if( d[G[i].to] > cnt ){
				d[G[i].to] = cnt;
				nub[G[i].to] = s;
				q[++r] = G[i].to;
			}
		}
	}
}
void init(){
	read(n);read(m);
	int u=0,v=0,t=0;char ch;
	while( ch = getchar() ){
		if(ch < '!' ) continue;
		if( ch == 'Q' ){
			memset(d,0x7f,4*n + 12);
			BFS(1);
			read(t),printf("%d\n",nub[t]);
			break;
		}
		else if( ch == 'C' ){
            memset(d,0x7f,4*n + 12);
			BFS(1);
			read(t),BFS(t);
			break;
		}
		else{
			u = 0;
			while(u = u*10+ch-'0',ch=getchar(),ch>'!');
			read(v);
			add(u,v);
		}	
	}

	for(int i=1;i<=m-1;i++){
		while(ch=getchar(),ch<'!');
		read(t);
		if( ch == 'Q' ) printf("%d\n",nub[t]);
		else BFS(t);
	}
}

int main(){
	#define doo
	#ifdef doo
	    freopen("heoi2016_tree.in","r",stdin);
	    freopen("heoi2016_tree.out","w",stdout);
	#endif
		init();
	#ifdef doo
	    fclose(stdin);fclose(stdout);
	#endif
	return 0;
}