记录编号	440117	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	6.858 s
提交时间	2017-08-22 17:11:55	内存使用	53.72 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
inline int read(){
	int sum=0;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n;
}a[1000005];
int pre[1000005];
int tot;
inline void insert(int s,int e){
	a[++tot].e=e;
	a[tot].n=pre[s];
	pre[s]=tot;
}
int dep[1000005],fa[1000005],son[1000005],size[1000005];
inline void dfs1(int u){
	size[u]=1,son[u]=0;
	for(int i=pre[u];i!=-1;i=a[i].n){
		int e=a[i].e;
		if(e!=fa[u]){
			fa[e]=u;
			dep[e]=dep[u]+1;
			dfs1(e);
			size[u]+=size[e];
			if(size[e]>size[son[u]])
				son[u]=e;
		}
	}
}
int cnt;
int top[1000005],id[1000005],pos[1000005];
inline void dfs2(int u,int rt){
	top[u]=rt;
	id[u]=++cnt;
	pos[cnt]=u;
	if(son[u])
		dfs2(son[u],rt);
	else
		return;
	for(int i=pre[u];i!=-1;i=a[i].n){
		int e=a[i].e;
		if(e!=fa[u]&&e!=son[u])
			dfs2(e,e);
	}
}
int mx[4000005];
inline void pushup(int i){
	mx[i]=max(mx[i<<1],mx[i<<1|1]);
}
inline void update(int pos,int l,int r,int i){
	if(l==r){
		mx[i]=pos;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)
		update(pos,l,mid,i<<1);
	else
		update(pos,mid+1,r,i<<1|1);
	pushup(i);
}
inline int query(int ll,int rr,int l,int r,int i){
	if(ll<=l&&r<=rr)
		return mx[i];
	int mid=l+r>>1,ret=0;
	if(ll<=mid)
		ret=max(query(ll,rr,l,mid,i<<1),ret);
	if(mid<rr)
		ret=max(query(ll,rr,mid+1,r,i<<1|1),ret);
	return ret;
}
int n,q;
char op[2];
inline int ask(int x){
	int ret(1);
	while(x){
		int tmp=query(id[top[x]],id[x],1,n,1);
		if(tmp)
			ret=dep[ret]>dep[pos[tmp]]?ret:pos[tmp];
		x=fa[top[x]];
	}
	return ret;
}
int main(){
	int __size__ = 50 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),q=read();
	for(int i=1;i<n;++i){
		int x=read(),y=read();
		insert(x,y);
	}
	dfs1(1);
	dfs2(1,1);
	int x;
	update(id[1],1,n,1);
	for(int i=0;i<q;++i){
		scanf("%s",op);
		x=read();
		if(op[0]=='Q')
			printf("%d\n",ask(x));
		else
			update(id[x],1,n,1);
	}
	return 0;
}