记录编号	500130	评测结果	AAAAAAAAAA
题目名称	[SPOJ 2666] QTREE4	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.212 s
提交时间	2018-07-08 23:55:49	内存使用	141.27 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct binary_heap{
	priority_queue<int>a,b;
	binary_heap(){}
	void push(int x){a.push(x);}
	void erase(int x){b.push(x);}
	int top(){
		while(!b.empty()&&a.top()==b.top()){
			a.pop();
			b.pop();
		}
		if(!b.empty())assert(a.top()>b.top());
		return a.top();
	}
	void pop(){
		top();
		a.pop();
	}
	int top2(){
		int x=top();
		pop();
		int y=top();
		push(x);
		return x+y;
	}
	bool empty(){return a.size()==b.size();}
	int size(){return a.size()-b.size();}
}globl,heap[maxn],q[maxn][35];
void build(int,int,int,int);
int getcenter(int,int);
void getdis(int,int,int);
void modify(int);
vector<int>G[maxn],W[maxn];
int p[maxn],depth[maxn],d[maxn][35],id[maxn][35];
int qu[maxn],size[maxn],son[maxn];
bool vis[maxn],exist[maxn];
int n,m;
int main(){
	freopen("QTREE4.in","r",stdin);
	freopen("QTREE4.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)exist[i]=true;
	for(int i=1,x,y,z;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(y);
		W[x].push_back(z);
		G[y].push_back(x);
		W[y].push_back(z);
	}
	globl.push(0);
	build(1,0,n,0);
	scanf("%d",&m);
	int cnt=n;
	while(m--){
		char c;
		scanf(" %c",&c);
		if(c=='A'){
			if(cnt>1)printf("%d\n",globl.top());
			else if(cnt==1)printf("0\n");
			else printf("They have disappeared.\n");
		}
		else{
			int x;
			scanf("%d",&x);
			if(exist[x])cnt--;
			else cnt++;
			modify(x);
		}
	}
	return 0;
}
void build(int x,int k,int s,int pr){
	x=getcenter(x,s);
	vis[x]=true;
	p[x]=pr;
	depth[x]=k;
	heap[x].push(0);
	if(s<=1)return;
	for(int i=0;i<(int)G[x].size();i++)
		if(!vis[G[x][i]]){
			p[G[x][i]]=x;
			d[G[x][i]][k]=W[x][i];
			getdis(G[x][i],k,G[x][i]);
			heap[x].push(q[G[x][i]][k].top());
		}
	if(heap[x].size()>1)globl.push(heap[x].top2());
	for(int i=0;i<(int)G[x].size();i++)
		if(!vis[G[x][i]])build(G[x][i],k+1,size[G[x][i]],x);
}
int getcenter(int x,int s){
	int head=0,tail=0;
	qu[tail++]=x;
	while(head!=tail){
		x=qu[head++];
		size[x]=1;
		son[x]=0;
		for(int i=0;i<(int)G[x].size();i++)
			if(!vis[G[x][i]]&&G[x][i]!=p[x]){
				p[G[x][i]]=x;
				qu[tail++]=G[x][i];
			}
	}
	for(int i=tail-1;i;i--){
		x=qu[i];
		size[p[x]]+=size[x];
		if(size[x]>size[son[p[x]]])son[p[x]]=x;
	}
	x=qu[0];
	while(son[x]&&size[son[x]]*2>=s)x=son[x];
	return x;
}
void getdis(int x,int k,int rt){
	int head=0,tail=0;
	qu[tail++]=x;
	while(head!=tail){
		x=qu[head++];
		id[x][k]=rt;
		size[x]=1;
		q[rt][k].push(d[x][k]);
		for(int i=0;i<(int)G[x].size();i++)
			if(!vis[G[x][i]]&&G[x][i]!=p[x]){
				p[G[x][i]]=x;
				d[G[x][i]][k]=d[x][k]+W[x][i];
				qu[tail++]=G[x][i];
			}
	}
	for(int i=tail-1;i;i--){
		x=qu[i];
		size[p[x]]+=size[x];
	}
}
void modify(int x){
	if(heap[x].size()>1)globl.erase(heap[x].top2());
	if(exist[x])heap[x].erase(0);
	else heap[x].push(0);
	if(heap[x].size()>1)globl.push(heap[x].top2());
	for(int u=p[x],k=depth[x]-1;u;u=p[u],k--){
		if(heap[u].size()>1)globl.erase(heap[u].top2());
		if(!q[id[x][k]][k].empty())heap[u].erase(q[id[x][k]][k].top());
		if(exist[x])q[id[x][k]][k].erase(d[x][k]);
		else q[id[x][k]][k].push(d[x][k]);
		if(!q[id[x][k]][k].empty())heap[u].push(q[id[x][k]][k].top());
		if(heap[u].size()>1)globl.push(heap[u].top2());
	}
	exist[x]^=true;
}