rt，悬赏 2 关注

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,tot,lg,mn=1e9,p,ans,cnt;
int ver[2*N],nxt[2*N],head[N],zt[N],dep[N],f[N][18],v[N],sz[N],fah[N],val[N];
multiset<int> s[N],t,u[N];
multiset<int>::iterator it;
void add(int x,int y){ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
int lca(int x,int y)
{
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=lg;i>=0;i--) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
	if(x==y) return x;
	for(int i=lg;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
void dfs(int x,int fa)
{
	f[x][0]=fa,dep[x]=dep[fa]+1;
	for(int i=1;i<=lg;i++) f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nxt[i]) if(ver[i]!=fa) dfs(ver[i],x);
}
int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
int get(int x)
{
	int si=s[x].size();
	if(!si) return 0;
	if(si==1&&zt[x]<0) return 0;
	if(si==1){it=--s[x].end(); return *it;}
	int a,b;
	it=--s[x].end(),a=*it;
	if((it=s[x].find(a))!=s[x].end()) s[x].erase(it);
	it=--s[x].end(),b=*it;
	s[x].insert(a);
	return a+b;
}
void Size(int x,int fa,int dat,int s)
{
	sz[x]=1; int mx=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y==fa||v[y]) continue;
		Size(y,x,dat,s),sz[x]+=sz[y],mx=max(mx,sz[y]);
	}
	if(dat) return;
	mx=max(mx,s-sz[x]);
	if(mx<mn) mn=mx,p=x;
}
void solve(int x)
{
	v[x]=1;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(v[y]) continue;
		mn=1e9,Size(y,x,0,sz[y]),fah[p]=x,Size(p,0,1,sz[y]);
		solve(p);
	}
}
void add(int x)
{
	for(int i=x;fah[i];i=fah[i])
	{
	    int d=dis(x,fah[i]),a=0;
		if((it=t.find(val[fah[i]]))!=t.end()) t.erase(it);
	    if(u[i].size()) it=--u[i].end(),a=*it;
        if((it=s[fah[i]].find(a))!=s[fah[i]].end()) s[fah[i]].erase(it);
		u[i].insert(d),it=--u[i].end(),s[fah[i]].insert(*it);
		val[fah[i]]=get(fah[i]),t.insert(val[fah[i]]);
	}
	if(!t.size()) ans=0;
	else it=--t.end(),ans=*it;
}
void del(int x)
{
    for(int i=x;fah[i];i=fah[i])
    {
    	int d=dis(x,fah[i]),a=0,b=0;
    	if((it=t.find(val[fah[i]]))!=t.end()) t.erase(it);
    	it=--u[i].end(),a=*it;
    	if((it=s[fah[i]].find(a))!=s[fah[i]].end()) s[fah[i]].erase(it);
    	if((it=u[i].find(d))!=u[i].end()) u[i].erase(it);
    	if(u[i].size()) it=--u[i].end(),b=*it;
        s[fah[i]].insert(b);
        val[fah[i]]=get(fah[i]),t.insert(val[fah[i]]);
	}
	if(!t.size()) ans=0;
	else it=--t.end(),ans=*it;
}
int main()
{
	scanf("%d",&n),lg=(int)(log(n)/log(2));
	for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0),Size(1,0,0,n),Size(p,0,1,n),solve(p);
    for(int i=1;i<=n;i++) zt[i]=1,add(i);
    scanf("%d",&q),cnt=n;
    for(int i=1,x;i<=q;i++)
    {
    	char op; cin>>op;
    	if(op=='G') printf("%d\n",cnt>1?ans:(cnt==1?0:-1));
		else scanf("%d",&x),zt[x]=0-zt[x],cnt+=zt[x],zt[x]>0?add(x):del(x);
	}
	return 0;
}