70PTS求调

#include<bits/stdc++.h>
using namespace std;
#define res register int
const int N=5e5+5;
vector<int> tr[N<<2];
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
void insert(int i,int l,int r,int L,int R,int p){
	if(r<L||R<l)return;
	if(L<=l&&R>=r){
		tr[i].push_back(p);
		return;
	}
	insert(ls,l,mid,L,R,p),insert(rs,mid+1,r,L,R,p);
}
struct edge{
	int v,net;
}s[N<<1];
int n,m,fr[N],top,dep[N],stop,U,V;
inline void add(int u,int v){if(u!=v)s[++stop]={v,fr[u]},fr[u]=stop;}
int st[N<<1][25],lg2[N<<1],ol[N],ltop;
void dfs(int u,int fa){
	dep[u]=dep[fa]+1,st[++ltop][0]=u,ol[u]=ltop;
	for(res v,i=fr[u];i;i=s[i].net){
		v=s[i].v;
		if(v==fa)continue;
		dfs(v,u),st[++ltop][0]=u;
	}
}
void st_init(){
	for(res i=2;i<=ltop;i++)lg2[i]=lg2[i>>1]+1;
	for(res i=1;i<=lg2[ltop];i++)for(res j=1;j<=ltop;j++){
		if(dep[st[j+(1<<(i-1))][i-1]]<dep[st[j][i-1]])st[j][i]=st[j+(1<<(i-1))][i-1];
		else st[j][i]=st[j][i-1];
	}
}
inline int Lca(int a,int b){
	int fa=ol[a],fb=ol[b];
	if(fa>fb)swap(fa,fb);
	if(dep[st[fa][lg2[fb-fa]]]<dep[st[fb-(1<<lg2[fb-fa])+1][lg2[fb-fa]]])return st[fa][lg2[fb-fa]];
	else return st[fb-(1<<lg2[fb-fa])+1][lg2[fb-fa]];
}
inline int dis(int u,int v){
	int lca=Lca(u,v);
	return dep[u]+dep[v]-(dep[lca]<<1);
}
int las[N],ans[N];
bitset<N> nd,now;
stack<pair<int,int>> sta;
void solve(int i,int l,int r){
	int now=sta.size();
	for(auto p:tr[i]){
		sta.push({U,V});
		if(!U&&!V)U=p,V=p;
		else{
			int d0=dis(U,V),d1=dis(V,p),d2=dis(U,p),d=max(d0,max(d1,d2));
			if(d==d1)U=p;
			else if(d==d2)V=p;
		}
	}
	if(l==r)ans[l]=(!U&&!V?-1:dis(U,V));
	else solve(ls,l,mid),solve(rs,mid+1,r);
	while(now!=sta.size()){
		pair<int,int> p=sta.top();
		sta.pop(),U=p.first,V=p.second;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(res i=1,u,v;i<n;i++)cin>>u>>v,add(u,v),add(v,u);
	dfs(1,0),st_init();
	cin>>m;
	for(res i=1,in2;i<=m;i++){
		char in;
		cin>>in;
		if(in=='G')nd[i]=1;
		else if(in=='C'){
			cin>>in2;
			if(!now[in2])now[in2]=1,insert(1,1,m,las[in2],i,in2);
			else now[in2]=0,las[in2]=i;
		}
	}
	for(res i=1;i<=n;i++)if(!now[i])insert(1,1,m,las[i],m,i);
	solve(1,0,m);
	for(res i=0;i<=m;i++)if(nd[i])cout<<ans[i]<<'\n';
	return 0;
}