记录编号	336623	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 树	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.510 s
提交时间	2016-11-03 15:17:28	内存使用	4.15 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cctype>
#define file(x) "heoi2016_tree."#x
using std::swap;
const int V=1e5+10,L=1<<15;
namespace I{
	char buf[L],*s,*t;
	inline char gc(){
		if(s==t) t=(s=buf)+fread(buf,1,L,stdin);
		if(s==t) return EOF;
		return *s++;
	}
	char nwc(){
		char ch=gc();
		if(!isalpha(ch)) ch=gc();
		return ch;
	}
	inline int gi(){
		int r=0,ch=gc();
		while(!(ch<='9'&&ch>='0')) ch=gc();
		while(ch<='9'&&ch>='0') r=r*10+ch-'0',ch=gc();
		return r;
	}
}using I::gi;using I::nwc;
int n,q,dfn[V],sz[V],top[V],fa[V],a[V],son[V],dfnclk,dec[V];
std::vector<int> to[V];
inline int lb(int x){return x&-x;}
void add(int p,int x){
	while(p<=n) a[p]+=x,p+=lb(p);
}
int pre(int p){
	if(!p) return 0;
	int s=0;
	while(p)
		s+=a[p],p-=lb(p);
	return s;
}
inline int sum(int l,int r){return pre(r)-pre(l-1);}
void dfs1(int u){
	int v;
	sz[u]=1;
	for(int i=0;i<to[u].size();i++) if((v=to[u][i])!=fa[u]){
		fa[v]=u;
		dfs1(v);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int nt){
	dec[dfn[u]=++dfnclk]=u;
	top[u]=nt;
	int v;
	if(son[u]) dfs2(son[u],nt);
	for(int i=0;i<to[u].size();i++) if((v=to[u][i])!=fa[u]&&v!=son[u]){
		dfs2(v,v);
	}
}
int solve(int a){
	while(!sum(dfn[top[a]],dfn[a])) a=fa[top[a]];
	int l=dfn[top[a]],r=dfn[a],mid;
	while(l<r){
		mid=l+r+1>>1;
		if(sum(mid,r)) l=mid;
		else r=mid-1;
	}
	return dec[l];
}
char s[2];
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	//scanf("%d%d",&n,&q);
	n=gi(),q=gi();
	for(int i=1;i<n;i++) {
		int u=gi(),v=gi();
		to[u].push_back(v);
		to[v].push_back(u);
	}
	dfs1(1),dfs2(1,1);
	add(dfn[1],1);
	for(int i=1;i<=q;i++){
		int t;
		t=nwc();
		if(t=='C') add(dfn[gi()],1);
		else if(t=='Q') printf("%d\n",solve(gi()));
	}
}