Rt，求助一个很多人求助的问题，就是大常数点分树如何卡过最后一个点的时限。

用multiset维护的，没想清楚堆怎么维护删除操作啊

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int n,h[N],tot,fa[N],f[N<<1][18],sz[N],v[N],d[N],dfn[N],T,t,lg[N<<1],u[N];
struct edge{int to,nxt;}e[N<<1];
void add(int x,int y){e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;}
void init(int x,int y){
	f[dfn[x]=++T][0]=x;d[x]=d[y]+1;
	for(int i=h[x];i;i=e[i].nxt)if(e[i].to!=y)init(e[i].to,x);
	f[++T][0]=y;
}
inline int ck(int x,int y){if(d[x]<d[y])return x;return y;}
int w,ed,mx;
multiset<int>sa[N],sb[N],sc;
void find(int x,int y){
	int cur=0;sz[x]=1;
	for(int i=h[x];i;i=e[i].nxt)if(e[i].to!=y&&!v[e[i].to])
		find(e[i].to,x),cur=max(cur,sz[e[i].to]),sz[x]+=sz[e[i].to];
	cur=max(cur,w-sz[x]);
	if(cur<mx)mx=cur,ed=x;
}
int solve(int x,int csz){
	w=mx=csz;find(x,0);
	int rt=ed,now;v[rt]=1;
	for(int i=h[rt];i;i=e[i].nxt)if(!v[e[i].to]){
		if(sz[e[i].to]<sz[rt])now=solve(e[i].to,sz[e[i].to]);
		else now=solve(e[i].to,csz-sz[rt]);
		fa[now]=rt;
	}
	return rt;
}
int get(int l,int r){
	int cur=lg[r-l+1];
	return ck(f[l][cur],f[r-(1<<cur)+1][cur]);
}
int dis(int x,int y){
	int cur=get(min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
	return d[x]+d[y]-2*d[cur];
}
void modify(int x){
	if(u[x]){
		multiset<int>::iterator it ;
		int cur=x;while(cur){
			if(sb[cur].size()>1){
				it=sb[cur].end();
				it--;int sum=*it;
				it--;sum+=*it;
				sc.erase(sc.find(sum));
			}
			cur=fa[cur];
		}
		cur=x;while(fa[cur]){
			sb[fa[cur]].erase(sb[fa[cur]].find(*(--sa[cur].end())));
			sa[cur].erase(sa[cur].find(dis(x,fa[cur])));
			if(sa[cur].size())sb[fa[cur]].insert(*(--sa[cur].end()));
			cur=fa[cur];
		}
		sb[x].erase(sb[x].find(0));
		cur=x;while(cur){
			if(sb[cur].size()>1){
				it=sb[cur].end();
				it--;int sum=*it;
				it--;sum+=*it;
				sc.insert(sum);
			}
			cur=fa[cur];
		}
	}
	else{
		multiset<int>::iterator it ;
		int cur=x;while(cur){
			if(sb[cur].size()>1){
				it=sb[cur].end();
				it--;int sum=*it;
				it--;sum+=*it;
				sc.erase(sc.find(sum));
			}
			cur=fa[cur];
		}
		cur=x;while(fa[cur]){
			if(sa[cur].size())sb[fa[cur]].erase(sb[fa[cur]].find(*(--sa[cur].end())));
			sa[cur].insert(dis(x,fa[cur]));
			sb[fa[cur]].insert(*(--sa[cur].end()));
			cur=fa[cur];
		}
		sb[x].insert(0);
		cur=x;while(cur){
			if(sb[cur].size()>1){
				it=sb[cur].end();
				it--;int sum=*it;
				it--;sum+=*it;
				sc.insert(sum);
			}
			cur=fa[cur];
		}
	}
	u[x]^=1;
}
int main(){
	scanf("%d",&n);
	rep(i,2,n){
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}init(1,0);solve(1,n);t=log2(T);
	rep(j,1,t)rep(i,1,T-(1<<j)+1)f[i][j]=ck(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	lg[0]=-1;rep(i,1,T)lg[i]=lg[i>>1]+1;
	rep(i,1,n)modify(i);
	int m;scanf("%d",&m);
	char op[2];int x;
	while(m--){
		scanf("%s",op);
		if(*op=='G'){
			if(sc.size())printf("%d\n",*(--sc.end()));
			else printf("-1\n");
		}
		else scanf("%d",&x),modify(x);
	}
	return 0;
}