Description：

一棵边带权的树，两种操作：取反节点x的颜色，询问树中最远的两个白色节点的距离。

$1\leqslant n\leqslant 10^5$

Solution：

考虑边分治，就是每次找到一条两边最大的子树最小的边，然后递归分治，这样可以建出一棵树形的结构，称之为边分树，对于每个节点维护两个堆，堆里存着子树中所有的点到这条边的距离还有来自哪个点，每个点再开一个容器存储他对他的所有祖先的贡献的值，某个节点的 $mx$ 就是从两边的堆中各取一个的最大值和子树的 $mx$ 取最大值，这样边分树根节点的 $mx$ 就是整棵树的答案，修改时直接利用容器中存储的信息来更新祖先即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

struct edge

{

	int to,nxt,v;

}es[MAXN << 1],e[MAXN << 1];

int edgenums = 0,edgenum = 0;

int lins[MAXN],lin[MAXN];

void adds(int a,int b,int v)

{

	es[edgenums] = (edge){b,lins[a],v};lins[a] = edgenums++;

	es[edgenums] = (edge){a,lins[b],v};lins[b] = edgenums++;

	return;

}

void add(int a,int b,int v)

{

	e[edgenum] = (edge){b,lin[a],v};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],v};lin[b] = edgenum++;

	return;

}

int col[MAXN];

void rebuild(int k,int fa)

{

	int ff = 0;

	for(int i = lins[k];i != -1;i = es[i].nxt)

	{

		if(es[i].to == fa)continue;

		if(ff == 0)

		{

			add(k,es[i].to,es[i].v);

			ff = k;

		}

		else

		{

			int t = ++n;col[t] = 1;

			add(ff,t,0);add(t,es[i].to,es[i].v);

			ff = t;

		}

		rebuild(es[i].to,k);

	}

	return;

}

bool del[MAXN << 1];

int siz[MAXN];

void calc_siz(int k,int fa)

{

	siz[k] = 1;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(del[i >> 1] || e[i].to == fa)continue;

		calc_siz(e[i].to,k);

		siz[k] += siz[e[i].to];

	}

	return;

}

int ct,ctsiz;

int sum;

void find_ct(int k,int fa)

{

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(del[i >> 1] || e[i].to == fa)continue;

		find_ct(e[i].to,k);

		int vsiz = max(siz[e[i].to],sum - siz[e[i].to]);

		if(vsiz < ctsiz)

		{

			ct = i;

			ctsiz = vsiz;

		}

	}

}

#define INF 0x3f3f3f3f

int cnt;

struct disdata

{

	int k,d;

	disdata(int k_ = 0,int d_ = 0){k = k_;d = d_;}

	bool operator < (const disdata &k)const

	{

		return d < k.d;

	}

};

priority_queue<disdata> s[MAXN][2];

struct nodedata

{

	int bel,side,dis;

	nodedata(int b_,int s_,int d_){bel = b_;side = s_;dis = d_;}

};

vector<nodedata> ndata[MAXN];

void calc_dis(int k,int fa,int d,int rt,int side)

{

	if(col[k] == 0)

	{

		s[rt][side].push(disdata(k,d));

		ndata[k].push_back(nodedata(rt,side,d));

	}

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(del[i >> 1] || e[i].to == fa)continue;

		calc_dis(e[i].to,k,d + e[i].v,rt,side);

	}

	return;

}

int mx[MAXN],lc[MAXN],rc[MAXN],ctw[MAXN];

void update(int k)

{

	while(!s[k][0].empty() && col[s[k][0].top().k])s[k][0].pop();

	while(!s[k][1].empty() && col[s[k][1].top().k])s[k][1].pop();

	if(s[k][0].empty() || s[k][1].empty())mx[k] = 0;

	else mx[k] = s[k][0].top().d + s[k][1].top().d + ctw[k];

	if(lc[k] != 0)mx[k] = max(mx[k],mx[lc[k]]);

	if(rc[k] != 0)mx[k] = max(mx[k],mx[rc[k]]);

	return;

}

int divide(int k)

{

	calc_siz(k,0);

	ct = -1;ctsiz = INF;sum = siz[k];

	find_ct(k,0);

	if(ct == -1)return 0;

	int x = e[ct].to,y = e[ct ^ 1].to;

	del[ct >> 1] = true;

	int t = ++cnt;ctw[t] = e[ct].v;

	calc_dis(x,0,0,t,0);calc_dis(y,0,0,t,1);

	lc[t] = divide(x);rc[t] = divide(y);

	update(t);

	return t;

}

void setwhite(int k)

{

	for(int i = ndata[k].size() - 1;i >= 0;--i)

	{

		nodedata d = ndata[k][i];

		s[d.bel][d.side].push(disdata(k,d.dis));

		update(d.bel);

	}

}

void setblack(int k)

{

	for(int i = ndata[k].size() - 1;i >= 0;--i)

	{

		update(ndata[k][i].bel);

	}

	return;

}

char getc()

{

	char c = getchar();

	while(c != 'A' && c != 'C')c = getchar();

	return c;

}

int main()

{

	scanf("%d",&n);

	int a,b,c;

	memset(lin,-1,sizeof(lin));

	memset(lins,-1,sizeof(lins));

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		adds(a,b,c);

	}

	int white = n;

	rebuild(1,0);

	divide(1);

	int q;

	scanf("%d",&q);

	char ch;

	for(int i = 1;i <= q;++i)

	{

		ch = getc();

		if(ch == 'A')

		{

			if(white == 0)puts("They have disappeared.");

			else printf("%d\n",mx[1]);

		}

		else

		{

			scanf("%d",&a);

			col[a] ^= 1;

			if(col[a])setblack(a),--white;

			else setwhite(a),++white;

		}

	}

	return 0;

}