记录编号	254336	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.307 s
提交时间	2016-04-25 06:26:45	内存使用	6.39 MiB

#include<cstdio>
int MAX(int A,int B){return A>B?A:B;}
int n,q,shu,first[100010];
struct edge{int v,nx;}o[200010];
void add(int u,int v){
	o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;
}
int fa[100010],s[100010],son[100010];
void dfs1(int x,int last){
	s[x]=1;
	for(int i=first[x];i;i=o[i].nx)
	    if(o[i].v!=last){
			fa[o[i].v]=x,dfs1(o[i].v,x),s[x]+=s[o[i].v];
			if(s[son[x]]<s[o[i].v])son[x]=o[i].v;
	    }
}
int cnt,top[100010],id[100010],rid[100010];
void dfs2(int x){
	id[x]=++cnt,rid[cnt]=x;
	if(son[x])top[son[x]]=top[x],dfs2(son[x]);
	for(int i=first[x];i;i=o[i].nx)
	    if(o[i].v!=fa[x]&&o[i].v!=son[x])
	        top[o[i].v]=o[i].v,dfs2(o[i].v);
}
int ans,tr[500010];
void ADD(int l,int r,int t,int x){
	if(l==r){tr[t]=l;return;}
	int mid=l+r>>1;
	if(x<=mid)ADD(l,mid,t<<1,x);
	else ADD(mid+1,r,t<<1|1,x);
	tr[t]=MAX(tr[t<<1],tr[t<<1|1]);
}
int ask(int l,int r,int t,int L,int R){
	if(L<=l&&r<=R)return tr[t];
	int mid=l+r>>1;
	if(R<=mid)return ask(l,mid,t<<1,L,R);
	if(L>mid)return ask(mid+1,r,t<<1|1,L,R);
	return MAX(ask(l,mid,t<<1,L,R),ask(mid+1,r,t<<1|1,L,R));
}
void query(int x){
	for(ans=0;ans==0;x=fa[top[x]])
		ans=ask(1,n,1,id[top[x]],id[x]);
	printf("%d\n",rid[ans]);
}
int main(){
	freopen("heoi2016_tree.in","r",stdin);
	freopen("heoi2016_tree.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,1),top[1]=1,dfs2(1);
	char ch[3];int x;
	for(ADD(1,n,1,1);q--;){
		scanf("%s%d",ch,&x);
		if(ch[0]=='C')ADD(1,n,1,id[x]);
		else query(x);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}