记录编号	313952	评测结果	AAAAA
题目名称	[HZOI 2015]白黑树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.306 s
提交时间	2016-10-02 15:10:50	内存使用	22.22 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=500010;
int fa[N],son[N][2],s[N],key[N];//key为该子树上黑点个数 
int add[N];bool root[N];//增加标记,根标记 
struct edge{int f,t;}w[N];
int n,m,q,head[N],tail[N],next[N];
int now;bool c[N];//now为当前黑点个数,c为当前颜色 
inline void add_e(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
void dfs(int x){//初始化 
	root[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!root[w[i].t]){
		fa[w[i].t]=x;
		s[w[i].t]=root[w[i].t]=1;
		dfs(w[i].t);
	}
}
//namespace LCT{
	inline void update(int x){//动态更新 
		s[x]=s[son[x][0]]+s[son[x][1]]+1;
	}
	inline void rotate(int x){//上旋 
		int y=fa[x],z=fa[y];
		bool b=(x==son[y][1]);
		fa[son[y][b]=son[x][!b]]=y;
		fa[son[x][!b]=y]=x;
		fa[x]=z;
		if (y==son[z][0]) son[z][0]=x;else
		if (y==son[z][1]) son[z][1]=x;
		root[x]=root[y];
		root[y]=0;
		update(y);
		update(x);
	}
	inline void pushdown(int x){//下传标记 
		if (add[x]){
			int l=son[x][0],r=son[x][1];
			add[l]+=add[x];add[r]+=add[x];
			key[l]+=add[x];key[r]+=add[x];
			add[x]=key[0]=add[0]=0;
		}
	}
	inline void splay(int x){//旋至链顶 
		pushdown(x);
		while (!root[x]){
			int y=fa[x],z=fa[y];
			pushdown(z);pushdown(y);pushdown(x);
			if (root[y]){rotate(x);return;}
			if (x==son[y][0]) rotate(y==son[z][0]?y:x);
				else rotate(y==son[z][1]?y:x);
			rotate(x);
		}
	}
	inline void access(int x){//将x到根路径设为优先路径 
		splay(x);
		root[son[x][1]]=1;
		son[x][1]=0;
		update(x);
		while (fa[x]){
			int y=fa[x];
			splay(y);
			root[son[y][1]]=1;
			root[son[y][1]=x]=0;
			update(y);
			splay(x);
		}
	}
	inline void Add(int x,int d){//将x到根路径上数目修改掉 
		access(x);
		add[x]+=d;
		key[x]+=d;
	}
	int splay(int x,int k){//将以x为根的splay的第k个元素伸展到根,并返回该元素 
		int l=son[x][0],r=son[x][1],i=s[l]+1,ans;
		pushdown(x);
		if (i==k) return x;
		if (k<i) ans=splay(l,k),rotate(son[x][0]);
			else ans=splay(r,k-i),rotate(son[x][1]);
		return ans;
	}
//}
void erfen(int x,int l,int r){//子树x上二分 
	if (l==r){printf("%d\n",splay(x,l));return;}
	int mid=(l+r)/2,next=splay(x,mid+1);
	if (key[next]>=now) erfen(next,mid+1,r);
		else erfen(next,l,mid);
}
char ch[10];int x;
int main()
{
	freopen("C_Tree.in","r",stdin);
	freopen("C_Tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++){
		scanf("%d%d",&w[i].f,&w[i].t);
		w[i+n].f=w[i].t;w[i+n].t=w[i].f;
		add_e(w[i].f,i);add_e(w[i].t,i+n);
	}
	dfs(1);
	while (m--){
		scanf("%s%d",ch,&x);
		if (ch[0]=='M')
			if (c[x]) c[x]=0,now--,Add(x,-1);
				else c[x]=1,now++,Add(x,1);
		else
			if (now){access(x);erfen(x,1,s[x]);}
				else puts("-1");
	}
	return 0;
}