记录编号	489075	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007]捉迷藏	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	6.868 s
提交时间	2018-02-27 10:51:42	内存使用	11.38 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=1e5+10;
int n,now_cnt,q,tot,w[inf],fi[inf],nxt[inf<<1],to[inf<<1];
void link(int x,int y){
	to[++tot]=y;nxt[tot]=fi[x];fi[x]=tot;
}
int top[inf],Fa[inf],siz[inf],son[inf],dep[inf];
void dfs1(int x){
	siz[x]=1;
	for(int i=fi[x];i;i=nxt[i]){
		if(to[i]==Fa[x])continue;
		Fa[to[i]]=x;
		dep[to[i]]=dep[x]+1;
		dfs1(to[i]);
		siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[son[x]])son[x]=to[i];
	}
}
void dfs2(int x,int y){
	top[x]=y;
	if(son[x])dfs2(son[x],y);
	for(int i=fi[x];i;i=nxt[i]){
		if(top[to[i]])continue;
		dfs2(to[i],to[i]);
	}
}
int get_dis(int x,int y){
	int tmp=dep[x]+dep[y];
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=Fa[top[x]];
	}
	return tmp-min(dep[x],dep[y])*2;
}
struct ghb_heap{
	priority_queue<int>INS,DEL;
	void pop(){
		while(!DEL.empty() && INS.top()==DEL.top())
			INS.pop(),DEL.pop();
		INS.pop();
	}
	int top(){
		while(!DEL.empty() && INS.top()==DEL.top())
			INS.pop(),DEL.pop();
		return INS.top();
	}
	void insert(int x){
		INS.push(x);
	}
	void del(int x){
		DEL.push(x);
	}
	int size(){
		return INS.size()-DEL.size();
	}
	int longest(){
		while(!DEL.empty() && INS.top()==DEL.top())
			INS.pop(),DEL.pop();
		int u=INS.top();
		INS.pop();
		while(!DEL.empty() && INS.top()==DEL.top())
			INS.pop(),DEL.pop();
		int v=INS.top();
		INS.push(u);
		return u+v;
	}
}A[inf],B[inf],C;
int vis[inf],fa[inf];
int id,Min_size;
void getsize(int x,int f){
	siz[x]=1;
	for(int i=fi[x];i;i=nxt[i]){
		if(vis[to[i]] || to[i]==f)continue;
		getsize(to[i],x);
		siz[x]+=siz[to[i]];
	}
}
void getrt(int x,int f,int y){
	int tmp=-0x3fffffff;
	for(int i=fi[x];i;i=nxt[i]){
		if(vis[to[i]] || to[i]==f)continue;
		getrt(to[i],x,y);
		tmp=max(tmp,siz[to[i]]);
	}
	tmp=max(tmp,y-siz[x]);
	if(tmp<Min_size){
		Min_size=tmp;
		id=x;
	}
}
void dfs(int x,int f,int y){
	A[y].insert(get_dis(x,fa[y]));
	for(int i=fi[x];i;i=nxt[i]){
		if(vis[to[i]] || to[i]==f)continue;
		dfs(to[i],x,y);
	}
}
void work(int x){
	B[x].insert(0);
	if(!fa[x])return ;
	dfs(x,0,x);
	B[fa[x]].insert(A[x].top());
}
void Div(int x,int f){
	getsize(x,0);
	Min_size=0x3fffffff;
	getrt(x,0,siz[x]);
	int rt=id;
	vis[rt]=1;
	fa[rt]=f;
	work(rt);
	for(int i=fi[rt];i;i=nxt[i]){
		if(vis[to[i]])continue;
		Div(to[i],rt);
	}
	if(B[rt].size()>=2)C.insert(B[rt].longest());
}
void init(){
	dfs1(1);
	dfs2(1,1);
	Div(1,0);
}
void turnon(int x){
	if(B[x].size()>=2)C.del(B[x].longest());
	B[x].del(0);
	if(B[x].size()>=2)C.insert(B[x].longest());
	int now=x;
	while(fa[now]){
		if(B[fa[now]].size()>=2)C.del(B[fa[now]].longest());
		B[fa[now]].del(A[now].top());
		A[now].del(get_dis(x,fa[now]));
		if(A[now].size()>=1)B[fa[now]].insert(A[now].top());
		if(B[fa[now]].size()>=2)C.insert(B[fa[now]].longest());
		now=fa[now];
	}
}
void turnoff(int x){
	if(B[x].size()>=2)C.del(B[x].longest());
	B[x].insert(0);
	if(B[x].size()>=2)C.insert(B[x].longest());
	int now=x;
	while(fa[now]){
		if(B[fa[now]].size()>=2)C.del(B[fa[now]].longest());
		if(A[now].size()>=1)B[fa[now]].del(A[now].top());
		A[now].insert(get_dis(x,fa[now]));
		B[fa[now]].insert(A[now].top());
		if(B[fa[now]].size()>=2)C.insert(B[fa[now]].longest());
		now=fa[now];
	}
}
int main()
{
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	scanf("%d",&n);
	now_cnt=n;
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		link(x,y);link(y,x);
	}
	init();
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		char s[10];
		int x;
		scanf("%s",s);
		if(s[0]=='C'){
			scanf("%d",&x);
			if(w[x]){
				turnoff(x);
				now_cnt++;
			}
			else {
				turnon(x);
				now_cnt--;
			}
			w[x]^=1;
		}
		else {
			if(now_cnt==0)printf("-1\n");
			else if(now_cnt==1)printf("0\n");
			else printf("%d\n",C.top());
		}
	}
	return 0;
}