记录编号	411145	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007]捉迷藏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	6.233 s
提交时间	2017-06-03 21:14:08	内存使用	28.06 MiB

//点分治+陈丹琦分治
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+10,M=5e5+10;
int n,m,w[N],head[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
bool vis[N];
int size[N],big[N],root,tree_size;
void getroot(int x,int fa){
	size[x]=1;big[x]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (vis[v]||v==fa) continue;
		getroot(v,x);
		size[x]+=size[v];
		big[x]=max(big[x],size[v]);
	}
	if (size[x]>=tree_size/2&&big[x]<=tree_size/2) root=x;
}
int fa[N],h[N],dis[N][20],dep[N];
void geth(int x,int fa){
	dis[x][++h[x]]=dep[x];
	size[x]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (vis[v]||v==fa) continue;
		dep[v]=dep[x]+1;
		geth(v,x);
		size[x]+=size[v];
	}
}
void build(int x){
	vis[x]=1;dep[x]=0;geth(x,0);
	for (int i=head[x];i;i=next[i]){
		int v=w[i];
		if (vis[v]) continue;
		tree_size=size[v];
		getroot(v,0);
		fa[root]=x;
		build(root);
	}
}
int mp[N],cp[N],up[N];
void update(int x){
	int v=fa[x],D=up[x];
	if (x==mp[v]) return;
	if (x==cp[v]){if (D>up[mp[v]]) swap(mp[v],cp[v]);}
	else if (D>up[mp[v]]) cp[v]=mp[v],mp[v]=x;
	else if (D>up[cp[v]]) cp[v]=x;
}
void paint(int p){//将p染成黑色
	up[p+n]=0;
	update(p+n);
	for (int x=p;x;x=fa[x]){
		up[x]=max(up[x],dis[p][h[x]-1]);
		update(x);
	}
}
void clear(int p){
	for (p+=n;p;p=fa[p]) up[p]=-1e9;
}
int query(int p){//所有黑点到p距离最大值
	int ans=up[mp[p]];
	for (int x=p;fa[x];x=fa[x]){
		int v=fa[x];
		ans=max(ans,dis[p][h[v]]+up[x==mp[v]?cp[v]:mp[v]]);
	}
	return ans;
}
struct opt{int l,r,p,ans;};
int tp[N],L[N],Ans[M];bool ask[M];
vector<opt> Q;
void cdq(int l,int r,int cnt,int ans,vector<opt> v){
	vector<opt> left,right;
	int mid=(l+r)>>1;
	for (int i=v.size()-1;i>=0;i--){
		opt now=v[i];
		if (now.l<=l&&now.r>=r) cnt++,paint(now.p);
	}
	for (int i=v.size()-1;i>=0;i--){
		opt now=v[i];
		now.ans=max(now.ans,query(now.p));
		if (now.l<=l&&now.r>=r){ans=max(ans,now.ans);continue;}
		if (now.l<=mid) left.push_back(now);
		if (now.r>mid) right.push_back(now);
	}
	for (int i=v.size()-1;i>=0;i--){
		opt now=v[i];
		if (now.l<=l&&now.r>=r) clear(now.p);
	}
	if (l==r) return void(Ans[l]=cnt?ans:-1);
	cdq(l,mid,cnt,ans,left);
	cdq(mid+1,r,cnt,ans,right);
}
int main()
{
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	tree_size=n;getroot(1,0);build(root);
	up[0]=-1e9;
	for (int i=1;i<=n;i++) fa[i+n]=i,up[i]=up[i+n]=-1e9;
	scanf("%d",&m);
	char s[10];
	for (int i=1,x;i<=m;i++){
		scanf("%s",s);
		if (s[0]=='C'){
			scanf("%d",&x);
			if (tp[x]) L[x]=i;else Q.push_back((opt){L[x],i-1,x,0});
			tp[x]^=1;
		}
		else ask[i]=1;
	}
	for (int i=1;i<=n;i++)
		if (!tp[i]) Q.push_back((opt){L[i],m,i,0});
	cdq(1,m,0,0,Q);
	for (int i=1;i<=m;i++)
		if (ask[i]) printf("%d\n",Ans[i]);
	return 0;
}