记录编号	268100	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	6.804 s
提交时间	2016-06-11 21:40:37	内存使用	42.27 MiB

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
inline void in(int&x){for(x=getchar();x<48|x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&tmp<58;tmp=getchar())x=x*10+(tmp^48);}
int n,q,shu,first[1000010];
struct edge{int v,nx;}o[2000010];
inline void add(int u,int v){o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;}
int fa[1000010],s[1000010],son[1000010];
struct node{int x,id;
	inline friend bool operator<(const node&a,const node&b){return a.id<b.id;}
};
set<node>*st[1000010];
inline void dfs1(int x){
	s[x]=1;
	for(int i=first[x];i;i=o[i].nx){
		if(o[i].v==fa[x])continue;
		fa[o[i].v]=x,dfs1(o[i].v),s[x]+=s[o[i].v];
		if(s[son[x]]<s[o[i].v])son[x]=o[i].v;
	}
}
int id[1000010],top[1000010];
inline void dfs2(int x){
	id[x]=++id[0];
	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])continue;
		top[o[i].v]=o[i].v;
		st[o[i].v]=new set<node>;
		dfs2(o[i].v);
	}
}
inline int query(int x){
	for(;x;x=fa[top[x]])
		if(st[top[x]]->size()&&(*st[top[x]]->begin()).id<=id[x])
			return (*(--st[top[x]]->upper_bound((node){0,id[x]}))).x;
	return 1;
}
char ch[2];
int main(){
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	int __size__ = 50 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	in(n),in(q);
	for(int i=1,u,v;i<n;++i)in(u),in(v),add(u,v),add(v,u);
	dfs1(1);
	top[1]=1,st[1]=new set<node>;
	dfs2(1);
	for(int x;q--;){
		scanf("%s",ch),in(x);
		if(*ch=='Q')printf("%d\n",query(x));
		else st[top[x]]->insert((node){x,id[x]});
	}
	//while(1);
}