记录编号	358160	评测结果	AAAAAAAAAA
题目名称	[SPOJ 2666] QTREE4	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	1.989 s
提交时间	2016-12-14 18:18:29	内存使用	49.52 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 4e5 + 10;
const int LEFT = 0;
const int RIGHT = 1;
const int INF = 2e9;


#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	bool han = false;
	int res = 0;
	
	while (not is_num(tmp)) { 
		if (tmp == '-') han = true;
		tmp = getchar();
	}
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return han ? -res : res;
}


#define is_ch(x) (x == 'C' or x == 'A')
inline int get_han() {
	char tmp = getchar();

	while (not is_ch(tmp)) tmp = getchar();
	
	return (tmp == 'C' ? 1 : 2);
}


class Tree {
public:
	struct Edge {
		int to, ne, v;
		Edge() {}
		Edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
	} e[MAXN << 1];
	
	int head[MAXN], ecnt;
	
	inline void add_edge(int fr, int to, int v) {
		e[++ecnt] = Edge(to, head[fr], v), head[fr] = ecnt;
		e[++ecnt] = Edge(fr, head[to], v), head[to] = ecnt;
	}
} ori, tra;


struct Node {
	int id, dis;
	Node() { id = 0, dis = INF; }
	Node(int id_, int dis_) { id = id_, dis = dis_; }
	
	bool operator < (const Node &b) const { return dis == b.dis ? id < b.id : dis < b.dis; }
};


struct EdgeDivide {
	priority_queue <Node> lt, rt;
	int ls, rs;
	int ans, v;
} ed[MAXN];


struct FatherDivide {
	int fa_div, dire, dis;
	FatherDivide() {}
	FatherDivide(int fa_div_, int dire_, int dis_) { fa_div = fa_div_, dire = dire_, dis = dis_; }
};


int del[MAXN];
int cost[MAXN];
bool ava[MAXN];
int sz[MAXN];
vector <FatherDivide> belong[MAXN];
int global_sz;
int ncnt, dcnt;
int a_num;
int n, q;


void rebuild(int now, int fa) {
	int now_fa = 0;
	for (int i = ori.head[now]; i; i = ori.e[i].ne) {
		int to = ori.e[i].to;
		if (to == fa) continue;
		
		if (now_fa) {
			int ne_fa = ++ncnt;
			tra.add_edge(now_fa, ne_fa, 0);
			tra.add_edge(ne_fa, to, ori.e[i].v);
			now_fa = ne_fa;
		} else {
			now_fa = now;
			tra.add_edge(now_fa, to, ori.e[i].v);
		}
		rebuild(to, now);
	}
}


void cal_size(int now, int fa) {
	sz[now] = 1;
	
	for (int i = tra.head[now]; i; i = tra.e[i].ne) {
		int to = tra.e[i].to;
		if (to == fa or del[i]) continue;
		
		cal_size(to, now);
		sz[now] += sz[to];
	}
}


int cal_edge(int now, int fa) {
	int now_ans = 0;
	
	for (int i = tra.head[now]; i; i = tra.e[i].ne) {
		int to = tra.e[i].to;
		if (to == fa or del[i]) continue;
		
		int tmp = cal_edge(to, now);
		if (cost[now_ans] > cost[tmp]) now_ans = tmp;
		
		cost[i] = max(sz[to], global_sz - sz[to]);
		if (cost[now_ans] > cost[i]) now_ans = i;
	}
	
	return now_ans;
}


inline void update(int tar) {
	while ((not ed[tar].lt.empty()) and (not ava[ed[tar].lt.top().id])) ed[tar].lt.pop();
	while ((not ed[tar].rt.empty()) and (not ava[ed[tar].rt.top().id])) ed[tar].rt.pop();
	
	if (ed[tar].rt.empty() or ed[tar].lt.empty()) ed[tar].ans = 0;
	else ed[tar].ans = ed[tar].rt.top().dis + ed[tar].lt.top().dis + ed[tar].v;
	
	ed[tar].ans = max(ed[tar].ans, ed[ed[tar].ls].ans);
	ed[tar].ans = max(ed[tar].ans, ed[ed[tar].rs].ans);
} 


void cal_div(int now, int fa, int tar, int dire, int de) {
	if (now <= n and now >= 1) {
		if (dire == LEFT) ed[tar].lt.push(Node(now, de));
		else ed[tar].rt.push(Node(now, de));
		belong[now].push_back(FatherDivide(tar, dire, de));
	}
	
	for (int i = tra.head[now]; i; i = tra.e[i].ne) {
		int to = tra.e[i].to;
		if (to == fa or del[i]) continue;
		
		cal_div(to, now, tar, dire, de + tra.e[i].v);
	}
}


int init_div(int now) {
	cal_size(now, 0);
	global_sz = sz[now];
	int mx_e = cal_edge(now, 0);
	if (mx_e == 0) return 0;
	int fr, to, tar;
	
	fr = tra.e[mx_e].to;
	to = (mx_e & 1) ? tra.e[mx_e + 1].to : tra.e[mx_e - 1].to;
	
	del[mx_e] = true;
	(mx_e & 1) ? del[mx_e + 1] = true : del[mx_e - 1] = true;
	
	tar = ++dcnt;
	cal_div(fr, 0, tar, LEFT, 0);
	cal_div(to, 0, tar, RIGHT, 0);
	
	ed[tar].ls = init_div(fr);
	ed[tar].rs = init_div(to);
	ed[tar].v = tra.e[mx_e].v;
	
	update(tar);
	// printf("now = %d fr = %d to = %d ls = %d rs = %d ans = %d\n", tar, fr, to, ed[tar].ls, ed[tar].rs, ed[tar].ans);
	return tar;
}


inline void change(int tar) {
	if (ava[tar]) {
		a_num--, ava[tar] = false;
		for (int i = belong[tar].size() - 1; i >= 0; i--) update(belong[tar][i].fa_div);
	} else {
		int fa_div, dire, dis;
		a_num++, ava[tar] = true;
		for (int i = belong[tar].size() - 1; i >= 0; i--) {
			fa_div = belong[tar][i].fa_div;
			dire = belong[tar][i].dire;
			dis = belong[tar][i].dis;
			
			if (dire == RIGHT) ed[fa_div].rt.push(Node(tar, dis));
			else ed[fa_div].lt.push(Node(tar, dis));
			update(fa_div);
		}
	}
	// printf("now = %d ls = %d rs = %d ans = %d\n", tar, ed[tar].ls, ed[tar].rs, ed[tar].ans);
}


inline void read() {
	n = get_num();
	int fr, to, v;
	for (int i = 1; i <= n - 1; i++) {
		fr = get_num(), to = get_num(), v = get_num();
		ori.add_edge(fr, to, v);
	}
}


void out(int now, int fa) {
	printf("fa = %d:\nson = ", now);
	for (int i = tra.head[now]; i; i = tra.e[i].ne) {
		int to = tra.e[i].to;
		if (to == fa) continue;
		
		printf("%d ", to);
	}
	printf("\n");
	
	for (int i = tra.head[now]; i; i = tra.e[i].ne) {
		int to = tra.e[i].to;
		if (to == fa) continue;
		
		out(to, now);
	}
}


inline void solve() {
	memset(ava, 1, sizeof(ava));
	ncnt = n;
	a_num = n;
	rebuild(1, 0);
	// out(1, 0);
	// for (int i = 1; i <= ncnt; i++) ava[i] = true;
	
	cost[0] = INF;
	init_div(1);
	
	q = get_num();
	while (q--) {
		int han = get_han();
		if (han == 1) {
			han = get_num();
			change(han);
		} else {
			if (a_num != 0) printf("%d\n", ed[1].ans);
			else printf("They have disappeared.\n");
		}
	}
}

int main() {
	freopen("QTREE4.in", "r", stdin);
	freopen("QTREE4.out", "w", stdout);
	read();
	solve();
	return 0;
}