看到单点修改，求全局白色的最远距离，可以使用点分树。
考虑维护这棵点分树，想想树的直径的 dp 求法：\(f_u = \max\{f_v + w(u, v)\}\)，答案为 \(\max(f_v+f_{v'})(v,v'\in \{\text{son}_u\})\)，\(\{\text{son}_i\}\) 表示 \(i\) 的孩子集合。
这时候维护就十分简单了，对于每个点都记录两个可重集，分别表示 \(u\) 的儿子的子树的最大深度和 \(u\) 的子树内所有点到 \(fa_u\) 的距离，\(fa_u\) 表示 \(u\) 在点分树上的父亲节点，分别记这两个可重集为 \(A_i,B_i\)，则 \(A_i = \{x|x=\max(B_v)\}\)。每次直接进行更新即可。最后还需记录一个可重集表示 \(\{f_i\}\)。
但是 multiset 速度太慢，有一个小技巧，就是记录两个堆，一个是原集合，一个是懒惰删除的堆，这样速度可以快很多。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector < int >
#define eb emplace_back
#define pii pair < int, int >
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
bool Mbe;
mt19937_64 rng(35);
constexpr int N = 1e5 + 10;
struct Heap {
priority_queue < int > pq, del;
void push(int x) {
pq.push(x);
}
void ers(int x) {
del.push(x);
}
int top() {
while(!del.empty() && pq.top() == del.top()) {
pq.pop();
del.pop();
}
return pq.top();
}
void pop() {
while(!del.empty() && pq.top() == del.top()) {
pq.pop();
del.pop();
}
pq.pop();
}
int sstop() {
int tmp = top();
pop();
int res = tmp + top();
push(tmp);
return res;
}
int size() {
return pq.size() - del.size();
}
};
struct edge {
int to, w, nxt;
} e[N << 1];
int n, q, rt, dn;
int dep[N];
int a[N], mx[N], sz[N], vis[N], dfn[N], mi[20][N], fa[N];
int head[N], cnt_e;
void adde(int u, int v, int w) {
++cnt_e, e[cnt_e].to = v, e[cnt_e].w = w, e[cnt_e].nxt = head[u], head[u] = cnt_e;
}
void dfs(int u, int ff) {
mi[0][dfn[u] = ++dn] = ff;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == ff) continue;
dep[v] = dep[u] + e[i].w;
dfs(v, u);
}
}
int get(int u, int v) {
return dfn[u] < dfn[v] ? u : v;
}
int lca(int u, int v) {
if(u == v) return u;
if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int d = __lg(v - u++);
return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
int dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void findroot(int u, int ff, int num) {
sz[u] = 1, mx[u] = 0;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == ff || vis[v]) continue;
findroot(v, u, num);
sz[u] += sz[v];
mx[u] = max(mx[u], sz[v]);
}
mx[u] = max(mx[u], num - sz[u]);
if(mx[u] < mx[rt]) rt = u;
}
Heap Ans, tx[N], di[N]; // 答案; 所有儿子的子树的最大深度; 子树内所有点到其父亲的距离.
void getdep(int u, int fath, int anc) {
di[anc].push(dis(u, fa[anc]));
sz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fath || vis[v]) continue;
getdep(v, u, anc);
sz[u] += sz[v];
}
}
void divide(int u) {
vis[u] = 1;
tx[u].push(0);
getdep(u, 0, u);
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(vis[v]) continue;
rt = 0;
findroot(v, u, sz[v]);
fa[rt] = u;
int tmp = rt;
divide(rt);
tx[u].push(di[tmp].top());
}
if(tx[u].size() >= 2) Ans.push(tx[u].sstop());
}
void ers(int u) {
if(tx[u].size() >= 2) Ans.ers(tx[u].sstop());
}
void push(int u) {
if(tx[u].size() >= 2) Ans.push(tx[u].sstop());
}
void update0(int u) {
ers(u);
tx[u].push(0);
push(u);
for(int x = u; fa[x]; x = fa[x]) {
ers(fa[x]);
if(di[x].size()) tx[fa[x]].ers(di[x].top());
di[x].push(dis(u, fa[x]));
tx[fa[x]].push(di[x].top());
push(fa[x]);
}
}
void update1(int u) {
ers(u);
tx[u].ers(0);
push(u);
for(int x = u; fa[x]; x = fa[x]) {
ers(fa[x]);
tx[fa[x]].ers(di[x].top());
di[x].ers(dis(u, fa[x]));
if(di[x].size()) tx[fa[x]].push(di[x].top());
push(fa[x]);
}
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
// freopen("data.in", "r", stdin);
// freopen("myans.out", "w", stdout);
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
adde(u, v, w);
adde(v, u, w);
}
dfs(1, 0);
for(int i = 1; i <= __lg(n); ++i)
for(int j = 1; j + (1 << i) - 1 <= n; ++j)
mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
mx[0] = N;
findroot(1, 0, n);
divide(rt);
cin >> q;
for(int qi = 1, tot = n; qi <= q; ++qi) {
char opt;
cin >> opt;
if(opt == 'C') {
int x;
cin >> x;
a[x] ^= 1;
if(a[x]) update1(x), --tot;
else update0(x), ++tot;
} else {
if(!tot) cout << "They have disappeared.\n";
else if(tot == 1) cout << 0 << "\n";
else cout << max(Ans.top(), 0) << "\n";
}
}
cerr << TIME << "ms\n";
return 0;
}