记录编号	365499	评测结果	AAAAAAAAAA
题目名称	[SPOJ 2666] QTREE4	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	4.643 s
提交时间	2017-01-20 17:25:06	内存使用	141.17 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 100005, maxd = 32, inf = 0x3f3f3f3f;
struct Edge {
	int next, to, dis;
	Edge(int a=0, int b=0, int c=0) :
		next(a), to(b), dis(c) {}
} e[maxn<<1];
int head[maxn], tot;
void Add(int u, int v, int w) {
	e[++tot] = Edge(head[u], v, w); head[u] = tot;
}
int N, size[maxn], F, Size, root;
int white[maxn], White, dis[maxn][maxd], rt[maxn][maxd], id[maxn][maxd];
bool vis[maxn];

struct heap {
	priority_queue<int> q, d;
	inline void refresh() 
	 { while(!d.empty() && q.top()==d.top()) q.pop(), d.pop();}
	void push(int x) { q.push(x); }
	void erase(int x) { d.push(x); }
	int top() { 
		refresh(); 
		if(!q.empty()) return q.top(); 
		else return -inf;
	} // notice
	void pop() { refresh(); q.pop(); }
	int size() { return q.size()-d.size(); }
	bool empty() { return !size(); }
};
heap Hp, hp[maxn], hhp[maxn][maxd];
inline int Dis(int x) {
	if(hp[x].size()<2) return 0;
	int a = hp[x].top(); hp[x].pop();
	int b = hp[x].top(); hp[x].push(a);
	return a+b;
}
void change(int x) {
	white[x] ^= 1;
	if(white[x]) ++ White;
	else -- White;
	for(int i=1; rt[x][i]; ++i) {
		int Rt = rt[x][i], Id = id[x][i];
		Hp.erase(Dis(Rt));

		hp[Rt].erase(hhp[Id][i].top());
		if(white[x]) hhp[Id][i].push(dis[x][i]);
		else hhp[Id][i].erase(dis[x][i]);
		hp[Rt].push(hhp[Id][i].top()); //千万别扔进去0
		Hp.push(Dis(Rt));
	}
	Hp.erase(Dis(x));
	if(white[x]) hp[x].push(0);
	else hp[x].erase(0);
	Hp.push(Dis(x)); 
}
void getdep(int x, int fa, int Rt, int Id, int res) {
	hhp[Id][res].push(dis[x][res]); 
	rt[x][res] = Rt;
	id[x][res] = Id;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(to==fa || vis[to]) continue;
		dis[to][res] = dis[x][res]+e[i].dis;
		getdep(to, x, Rt, Id, res);
	}
}
void build(int x, int res) {
	hp[x].push(0); 
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		dis[to][res] = e[i].dis;
		getdep(to, x, x, to, res);
		hp[x].push(hhp[to][res].top());
	}
}
int getroot(int x, int fa) {
	int f=0; size[x] = 1;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to] || to==fa) continue;
		size[x] += getroot(to, x);
		f = max(f, size[to]);
	}
	f = max(f, Size-size[x]);
	if(f<=F) F = f, root = x;
	return size[x];
}
void Build(int x, int res) {
	vis[x] = 1; build(x, res);
	Hp.push(Dis(x));
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[to]) continue;
		F = Size = size[to]; getroot(to, -1);
		Build(root, res+1);
	}
}
int main() {
	freopen("QTREE4.in","r",stdin);
	freopen("QTREE4.out","w",stdout);
	scanf("%d", &N);
	for(int i=1,a,b,c; i<N; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		Add(a, b, c); Add(b, a, c);
	}

	White = N;
	for(int i=1; i<=N; ++i) white[i] = 1;
	F = Size = N; getroot(1, -1);
	Build(root, 1);

	int Q, v; char ch[2];
	scanf("%d", &Q);
	while(Q--) {
		scanf("%s", ch);
		if(ch[0]=='C') {
			scanf("%d", &v);
			change(v);
		} else {
			if(!White) puts("They have disappeared.");
			else if(White==1) puts("0");
			else printf("%d\n", max(0, Hp.top()));
		}
	}
	return 0;
}