orz

qtree4

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#define R(a) (abs(rand() * rand() + rand()) % (a) + 1)
#define sf(a) { key[a] = R(1000010); }
#define INF (1 << 29)
#define maxn 100100
#define Maxn 3101000
using namespace std;
struct str { int done,v,nex,len; } edge[maxn << 1];
char ch;
int ans,i,j,k,m,n,a,b,c,e = 1,T,s;
int first[maxn],l[maxn << 2],r[maxn << 2],pk[maxn << 2],root[maxn << 2],tot,top;
int val[Maxn],key[Maxn],kid[2][Maxn],sou[maxn][31],sum[maxn],p[maxn][31];
int que[maxn],h,t,f[maxn],dist[maxn][31],M[Maxn],N[Maxn];
int st[maxn],sq,mark[maxn],al = 0;

void make_edge(int a,int b,int c) {
	edge[++e].nex = first[a]; first[a] = e;
	edge[e].v = b; edge[e].len = c;
	edge[++e].nex = first[b]; first[b] = e;
	edge[e].v = a; edge[e].len = c;
}

void rotate(int ff,int f,int u) {
	int k = (kid[0][f] == u);
	if (ff) {
		if (kid[0][ff] == f) kid[0][ff] = u;
		else kid[1][ff] = u;
	}
	kid[k ^ 1][f] = kid[k][u];
	kid[k][u] = f;
}

void insert(int &root,int v,int &sou) {
	if (!sou) { val[++top] = v; sf(top); sou = top; }
	sq = 0; int u = root;
	if (!u) {
		root = sou; return;
	}
	while (true) {
		st[++sq] = u;
		if (v < val[u] || (v == val[u] && sou < u)) {
			if (kid[0][u]) u = kid[0][u];
			else { kid[0][u] = sou; break; }
		}else {
			if (kid[1][u]) u = kid[1][u];
			else { kid[1][u] = sou; break; }
		}
	}
	for (; sq; sq--) {
		if (key[st[sq]] < key[sou])
			rotate(st[sq - 1],st[sq],sou);
		else break;
	}
	if (!sq) root = sou;
}

void del(int &root,int v,int sou) {
	int u = root,f = 0;
	if (root == sou) {
		if (kid[0][root]) root = kid[0][root];
		else if (kid[1][root]) root = kid[1][root];
		else { root = 0; return; }
 	}
	while (u != sou) {
		f = u;
		if (v < val[u] || (v == val[u] && sou < u)) u = kid[0][u];
		else u = kid[1][u];
	}
	while (true) {
		if (kid[0][u]) {
			v = kid[0][u];
			rotate(f,u,kid[0][u]);
			f = v;
		}else if (kid[1][u]) {
			v = kid[1][u];
			rotate(f,u,kid[1][u]);
			f = v;
		}else break;
	}
	if (kid[0][f] == u) kid[0][f] = 0;
	else kid[1][f] = 0;
}

int bfs(int num,int base,int deep,int &root,int mark) {
	int u,v,i; s = t = 0;
	que[++t] = base; f[base] = 0; dist[base][deep] = 0;
	while (s < t) {
		u = que[++s]; p[u][deep] = mark;
		for (i = first[u]; i; i = edge[i].nex) {
			if (f[u] == edge[i].v || edge[i].done) continue;
			que[++t] = edge[i].v; f[edge[i].v] = u;
			dist[edge[i].v][deep] = dist[u][deep] + edge[i].len;
			insert(root,dist[edge[i].v][deep],sou[edge[i].v][deep]);
		}
	}
	int an = INF, ans = 0;
	for (; t; t--) {
		u = que[t]; sum[u] = 1;
		for (i = first[u]; i; i = edge[i].nex) {
			if (f[u] == edge[i].v || edge[i].done) continue;
			sum[u] += sum[edge[i].v];
			if (abs(num - (an << 1)) > abs(num - (sum[edge[i].v] << 1))) {
				an = sum[edge[i].v];
				ans = i;
			}
		}
	}
	edge[ans].done = edge[ans ^ 1].done = 1;
	return ans;
}

int find(int u) {
	return (kid[1][u] ? find(kid[1][u]) : val[u]);
}

int init(int base,int num,int deep,int mark) {
	int u = ++tot;
	int i,k,js;
	root[u] = ++top; val[top] = 0; sf(top);
	sou[base][deep] = top;
	k = bfs(num,base,deep,root[u],mark); pk[u] = k;
	if (num == 1) return u; js = sum[edge[k].v];
	l[u] = init(edge[k].v,js,deep + 1,0);
	r[u] = init(edge[k ^ 1].v,num - js,deep + 1,1);
	N[u] = find(root[u]);
	M[u] = max(M[l[u]],M[r[u]]);
	M[u] = max(M[u],N[l[u]] + N[r[u]] + edge[k].len);
	ans = max(ans,M[u]);
	return u;
}

int change(int u,int base,int deep,int mark) {
	if (!base) return 0;
	if (mark) insert(root[base],dist[u][deep],sou[u][deep]);
	else del(root[base],dist[u][deep],sou[u][deep]);
	N[base] = find(root[base]);
	if (p[u][deep + 1]) change(u,r[base],deep + 1,mark);
	else change(u,l[base],deep + 1,mark);
	M[base] = max(M[l[base]],M[r[base]]);
	if (root[l[base]] && root[r[base]])
		M[base] = max(M[base],N[l[base]] + N[r[base]] + edge[pk[base]].len);
	ans = max(ans,M[base]);
}

int main() {
	freopen("qtree4.in","r",stdin);
	freopen("qtree4.out","w",stdout);
	scanf("%d",&n); al = n;
	for (i = 1; i < n; i++) {
		scanf("%d %d %d",&a,&b,&c);
		make_edge(a,b,c);
	}
	init(1,n,0,0);
	scanf("%d",&T);
	for (; T; T--) {
		do ch = getchar(); while (ch != 'A' && ch != 'C');
		if (ch == 'A') {
			if (al) printf("%d\n",ans);
			else puts("They have disappeared.");
		}
		else {
			ans = 0; scanf("%d",&a);
			al += mark[a] - (mark[a] ^ 1);
			change(a,1,0,mark[a]);
			mark[a] ^= 1;
		}
	}
	return 0;
}