记录编号	223826	评测结果	AAAAAAAAAA
题目名称	[SPOJ 2666] QTREE4	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	2.906 s
提交时间	2016-02-13 17:42:27	内存使用	85.16 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int SIZEN=410000;
int N;
bool co[SIZEN]={0};//0代表白，1代表黑
class point
{
public:
	int dist,x;
	bool operator < (const point &b) const
	{
		return dist<b.dist;
	}
};
class miku
{
    public:
	int fr,to,lo;
	bool type;
	miku(){}
	miku(int a,int b,int c)
	{
		fr=a,to=b,lo=c;
		type=1;
	}
}e[SIZEN],E[SIZEN];//
class poi//用来储存分治中每棵子树的信息
{
    public:
	int st;
	priority_queue<point> Q;
	int lc,rc;
	int midlen;
	int ans;
	void print()
	{
		cout<<"st:"<<st<<endl;
		cout<<lc<<" "<<rc<<endl;
		cout<<"midlen:"<<midlen<<endl;
		cout<<ans<<endl;
	}
}tr[SIZEN*4];
vector<int> s[SIZEN];//第一次建图时使用
vector<int> S[SIZEN];//第二次建图时使用
vector<pair<int,int> > c[SIZEN];
int tot=0;
int n;
int cnt;
int siz[SIZEN];
void add(int fr,int to,int lo)
{
	s[fr].push_back(tot);e[tot++]=miku(fr,to,lo);
	s[to].push_back(tot);e[tot++]=miku(to,fr,lo);
}
void ADD(int fr,int to,int lo)
{
	S[fr].push_back(tot);E[tot++]=miku(fr,to,lo);
	S[to].push_back(tot);E[tot++]=miku(to,fr,lo);
}
void read()
{
	scanf("%d",&N);
	int v,u,lo;
	for(int i=1;i<N;i++)
	{
		scanf("%d%d%d",&v,&u,&lo);
		add(v,u,lo);
	}
}
void check(int x,int fa)
{
	int father=0;
	for(int i=0;i<s[x].size();i++)
	{
		int v=e[s[x][i]].to,w=e[s[x][i]].lo;
		if(v==fa) continue;
		if(father==0)
		{
			ADD(x,v,w);
			father=x;
			check(v,x);
		}
		else
		{
			++n;co[n]=1;
			ADD(father,n,0);ADD(n,v,w);
			father=n;
			check(v,x);
		}
	}
}
void rebuilt()//添加虚点
{
	n=N;
	check(1,0);
}
void ADD1(int x,int y,int dist)
{
	c[x].push_back(make_pair(y,dist));
}
void getsize(int beg,int u,int fa,int dist)
{
	ADD1(u,beg,dist);if(!co[u]) tr[beg].Q.push((point){dist,u});
	siz[u]=1;
	for(int i=0;i<S[u].size();i++)
	{
		int v=E[S[u][i]].to,w=E[S[u][i]].lo;
		int ok=E[S[u][i]].type;
		if(v==fa||ok==0) continue;
		getsize(beg,v,u,dist+w);
		siz[u]+=siz[v];
	}
}
int midedge,mi;
void getmid(int beg,int u,int code)//寻找中心边
{
	if(max(siz[u],siz[tr[beg].st]-siz[u])<mi)
	{
		mi=max(siz[u],siz[tr[beg].st]-siz[u]);
		midedge=code;
	}
	for(int i=0;i<S[u].size();i++)
	{
		int tmp=S[u][i];
		int p=E[tmp].type;
		if(tmp==(code^1)||p==0) continue;
		getmid(beg,E[tmp].to,tmp);
	}
}
void push(int pt)
{
	tr[pt].ans=-1;
	while(!tr[pt].Q.empty()&&co[tr[pt].Q.top().x]==1) tr[pt].Q.pop();
	int lc=tr[pt].lc,rc=tr[pt].rc;
	if(tr[pt].lc==0&&tr[pt].rc==0)
	{
		if(!co[tr[pt].st]) tr[pt].ans=0;
	}
	else
	{
		if(tr[lc].ans>tr[pt].ans) tr[pt].ans=tr[lc].ans;
		if(tr[rc].ans>tr[pt].ans) tr[pt].ans=tr[rc].ans;
		if(!tr[lc].Q.empty()&&!tr[rc].Q.empty())
		{
			tr[pt].ans=max(tr[pt].ans,tr[lc].Q.top().dist+tr[rc].Q.top().dist+tr[pt].midlen);
		}
	}
}
void dfs(int pt,int u)
{
	tr[pt].st=u;
	getsize(pt,u,0,0);
	midedge=-1;mi=n;getmid(pt,u,-1);
	//cout<<pt<<" "<<midedge<<endl;
	if(midedge!=-1)
	{
		miku tmp=E[midedge];
		tr[pt].midlen=tmp.lo;
		E[midedge].type=0;
		E[midedge^1].type=0;
		dfs(tr[pt].lc=++cnt,tmp.fr);
		dfs(tr[pt].rc=++cnt,tmp.to);
	}
	push(pt);
}
void change(int x)
{
	co[x]^=1;
	if(co[x]==1)
		for(int i=c[x].size()-1;i>=0;i--)
		{
			push(c[x][i].first);
		}
	else
	{
		for(int i=c[x].size()-1;i>=0;i--)
		{
		tr[c[x][i].first].Q.push((point){c[x][i].second,x});
		push(c[x][i].first);
		}
	}
}
void work()
{
	int Q;
	scanf("%d",&Q);
	int x;
	char a[10];
	for(int i=1;i<=Q;i++)
	{
		//cout<<i<<endl;
		scanf("%s",a);
		if(a[0]=='A')
		{
			if(tr[1].ans==-1) printf("They have disappeared.\n");
			else printf("%d\n",tr[1].ans);
		}
		else
		{
			scanf("%d",&x);
			change(x);
		}
	}
}
int main()
{
	freopen("QTREE4.in","r",stdin);
	freopen("QTREE4.out","w",stdout);
	read();
	tot=0;
	rebuilt();
	dfs(cnt=1,1);
	work();
	return 0;
}