记录编号	362635	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	7.565 s
提交时间	2017-01-08 08:04:51	内存使用	43.22 MiB

#include<cstdio>
#include<vector>
#define M 1000005
using namespace std;
int n,m,cnt,ans;
int dep[M],L[M],R[M],S[M],lazy[M<<2];
bool vis[M];
vector<int> e[M];
void dfs()
{
	int x;
	S[++S[0]]=1;
	for (;S[0];)
	{
		x=S[S[0]];
		if (!vis[x])
		{
			L[x]=++cnt;
			for (int v,i=0;i<e[x].size();++i)
				v=e[x][i],
				dep[v]=dep[x]+1,
				S[++S[0]]=v;
			vis[x]=1;
		}
		else
			R[x]=cnt,
			--S[0];
	}
}
void update(int rt,int begin,int end,int l,int r,int x)
{
	if (l<=begin&&end<=r)
	{
		if (!lazy[rt]||dep[x]>dep[lazy[rt]])lazy[rt]=x;
		return;
	}
	int mid=(begin+end)>>1;
	if (mid>=l) update(rt<<1,begin,mid,l,r,x);
	if (mid<r) update(rt<<1|1,mid+1,end,l,r,x);
}
void get(int rt,int begin,int end,int pos)
{
	ans=(lazy[rt]&&dep[lazy[rt]]>dep[ans]?lazy[rt]:ans);
	if (begin==end) return;
	int mid=(begin+end)>>1;
	if (mid>=pos) get(rt<<1,begin,mid,pos);
	else get(rt<<1|1,mid+1,end,pos);
}
main()
{
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout); 
	scanf("%d%d",&n,&m);
	for (int u,v,i=1;i<n;++i)
		scanf("%d%d",&u,&v),
		e[u].push_back(v);
	dep[1]=1; 
	dfs();
	update(1,1,n,1,n,1);
	char opt;
	for (int num;m;--m)
	{
		opt=getchar();
		while (opt!='C'&&opt!='Q') opt=getchar();
		scanf("%d",&num);
		if (opt=='C') update(1,1,n,L[num],R[num],num);
		else ans=1,get(1,1,n,L[num]),printf("%d\n",ans); 
	} 
}