comes from FOTILE 点分治！

qtree4.cpp

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=~0U>>2;
int getint()
{
	int ret=0;bool ok=false,neg=false;
	for(;;)
	{
		int c=getchar();
		if(c>='0'&&c<='9')ret=(ret<<3)+ret+ret+c-'0',ok=true;
		else if(ok)return neg?-ret:ret;
		else if(c=='-')neg=true;
	}
}
int getalpha()
{
	int ret=getchar();
	while(!isalpha(ret))ret=getchar();
	return ret;
}
int n,Q;
struct edge
{
	int v,w;
	edge *n;
};
edge EPool[400001],*ep=EPool,*g[100001];
inline void addedge(int u,int v,int w)
{
	ep->v=v,ep->w=w,ep->n=g[u],g[u]=ep++;
}
bool black[100001],isdone[100001];
int NPool[1800001],Root[18][100001],Rlv[100001],Fa[18][100001],D[18][100001],S[100001],MaxS[100001];
int tlv,*beg[100001],*end[100001];
void dfs(int u,int fa,int *&p)
{
	*(p++)=u,S[u]=MaxS[u]=0;
	for(edge *i=g[u];i;i=i->n)if(i->v!=fa&&!isdone[i->v])
	{
		D[tlv][i->v]=D[tlv][u]+i->w,dfs(i->v,u,p),S[u]+=S[i->v];
		if(MaxS[u]<S[i->v])MaxS[u]=S[i->v];
	}S[u]++;
}
edge *G[100001];
inline void addedge(int u,int v)
{
	ep->v=v,ep->n=G[u],G[u]=ep++;
}
void process(int u,int lv,int *p)
{
	D[lv][u]=0,Rlv[u]=tlv=lv;isdone[u]=true,Fa[lv][u]=Root[lv][u]=u,addedge(u,u);
	for(edge *i=g[u];i;i=i->n)if(!isdone[i->v])addedge(u,i->v),D[lv][i->v]=i->w,beg[i->v]=p,dfs(i->v,u,p),end[i->v]=p;
	for(edge *i=g[u];i;i=i->n)if(!isdone[i->v])
	{
		int v=i->v;
		for(int *j=beg[v];j!=end[v];j++)Root[lv][*j]=u,Fa[lv][*j]=v,MaxS[*j]=max(MaxS[*j],S[v]-S[*j]);
	}
	for(edge *i=g[u];i;i=i->n)if(!isdone[i->v])
	{
		int v=i->v;
		for(int *j=beg[v];j!=end[v];j++)if((MaxS[*j]<<1)<=S[v])
		{
			process(*j,lv+1,p);
			break;
		}
	}
}
struct DType
{
	int u,d;
	bool operator < (const DType &k2) const {return d<k2.d;}
	DType(){}
	DType(int a,int b):u(a),d(b){}
};
priority_queue<DType> RHeap[100001],FHeap[18][100001],GHeap;
inline void MaintainFTop(priority_queue<DType> &Q)
{
	while(!Q.empty()&&black[Q.top().u])Q.pop();
}
inline void MaintainRTop(int u)
{
	int lv=Rlv[u];
	priority_queue<DType> &Q=RHeap[u];
	while(!Q.empty()&&(FHeap[lv][Q.top().u].empty()||Q.top().d>FHeap[lv][Q.top().u].top().d))Q.pop();
}
int GetRAns(int u)
{
	MaintainRTop(u);
	if(RHeap[u].empty())return black[u]?-inf:0;
	DType t=RHeap[u].top();
	int a1=t.d,ret=black[u]?-inf:a1;
	while(!RHeap[u].empty()&&RHeap[u].top().u==t.u)
	{
		while(!RHeap[u].empty()&&RHeap[u].top().u==t.u)RHeap[u].pop();
		MaintainRTop(u);
	}
	int a2=RHeap[u].empty()?-inf:RHeap[u].top().d;
	ret=max(ret,a1+a2);
	return RHeap[u].push(t),ret;
}
int RAns[100001];
inline void MaintainGTop()
{
	while(GHeap.top().d>RAns[GHeap.top().u])GHeap.pop();
}
int main()
{
	n=getint();
	for(int i=1;i<n;i++)
	{
		int u=getint(),v=getint(),w=getint();
		addedge(u,v,w),addedge(v,u,w);
	}
	int *ttttp=NPool;
	dfs(1,0,ttttp);
	for(int i=1;i<=n;i++)MaxS[i]=max(MaxS[i],n-S[i]);
	for(int i=1;i<=n;i++)if((MaxS[i]<<1)<=n)
	{
		process(i,0,NPool);
		break;
	}
	for(int i=1;i<=n;i++)
		for(int j=0;Fa[j][i];j++)FHeap[j][Fa[j][i]].push(DType(i,D[j][i]));
	for(int u=1;u<=n;u++)
	{
		int lv=Rlv[u];
		for(edge *i=G[u];i;i=i->n)RHeap[u].push(DType(i->v,FHeap[lv][i->v].top().d));
		RAns[u]=GetRAns(u),GHeap.push(DType(u,RAns[u]));
	}
	Q=getint();
	for(int i=1;i<=Q;i++)
	{
		int C=getalpha();
		if(C=='A')printf(GHeap.top().d==-inf?"They have disappeared.\n":"%d\n",GHeap.top().d);
		else
		{
			int u=getint();
			if(black[u])
			{
				black[u]=false;
				for(int j=0;Fa[j][u];j++)
				{
					int F=Fa[j][u],R=Root[j][u];
					bool yoo=FHeap[j][F].empty()?1:D[j][u]>FHeap[j][F].top().d;
					FHeap[j][F].push(DType(u,D[j][u]));
					if(yoo)
					{
						RHeap[R].push(DType(F,D[j][u]));
						int t=RAns[R],tt=RAns[R]=GetRAns(R);
						if(tt>t)GHeap.push(DType(R,tt));
					}
				}
			}
			else
			{
				black[u]=true;
				for(int j=0;Fa[j][u];j++)
				{
					int F=Fa[j][u],R=Root[j][u];
					if(FHeap[j][F].top().u==u)
					{
						MaintainFTop(FHeap[j][F]);
						RHeap[R].push(DType(F,FHeap[j][F].top().d));
						RAns[R]=GetRAns(R);
						GHeap.push(DType(R,RAns[R]));
						MaintainGTop();
					}
				}
			}
		}
	}
	return 0;
}