记录编号	399691	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]tree—增强版	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	6.948 s
提交时间	2017-04-27 13:34:16	内存使用	73.74 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
int n,q,w[N*2],head[N],next[N*2];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],s[N],dfn[N],big[N],link[N],pt[N];
void dfs(int x){
	s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i]]){
		int v=w[i];
		fa[v]=x;
		dfs(v);
		s[x]+=s[v];
		if (s[v]>s[big[x]]) big[x]=v;
	}
}
vector<int> Q[N];int id[N];
void po(int x){
	static int cnt=0;
	pt[dfn[x]=++cnt]=x;
	link[x]=(dfn[x]==dfn[fa[x]]+1?link[fa[x]]:x);
	Q[link[x]].push_back(x);
	id[x]=Q[link[x]].size()-1;
	if (!big[x]) return;
	po(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i]!=fa[x]&&w[i]!=big[x]) po(w[i]);
}
int Max[N*4];
#define lc x<<1
#define rc x<<1|1
void paint(int p){
	int x=1,l=1,r=n;
	while (1){
		Max[x]=max(Max[x],p);
		if (l==r) return;
		int mid=(l+r)>>1;
		if (p>mid) x=rc,l=mid+1;else x=lc,r=mid;
	}
}
int find(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return Max[x];
	int mid=(l+r)>>1,ans=0;
	if (L<=mid) ans=max(ans,find(lc,l,mid,L,R));
	if (R>mid) ans=max(ans,find(rc,mid+1,r,L,R));
	return ans;
}
bool vis[N];
int query(int x){//O(logn)
	while (!vis[x]) x=fa[link[x]];
	return pt[find(1,1,n,dfn[link[x]],dfn[x])];
}
void color(int p){//O(logn)
	vector<int> &q=Q[link[p]];
	for (int i=id[p];i<q.size();i++){
		int v=q[i];
		if (vis[v]) break;
		vis[v]=1;
	}
	paint(dfn[p]);
}
int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
void print(int x){
	static char str[20];
	int l=0;
	for (;x;x/=10) str[l++]=x%10;
	while (l) putchar('0'+str[--l]);
	putchar('\n');
}
int main()
{
	freopen("tree++.in","r",stdin);
	freopen("tree++.out","w",stdout);
	int __size__=32<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	scanf("%d%d",&n,&q);
	for (int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	fa[1]=1;dfs(1);po(1);color(1);
	while (q--){
		char s=0;
		while (s!='Q'&&s!='C') s=getchar();
		int x=read();
		if (s=='Q') print(query(x));else color(x);
	}
	return 0;
}