题意概述
有一棵$N$个节点的树，每个节点都是黑色或白色。有$Q$次操作，动态修改点的颜色，询问最远黑点对之间的距离。
数据范围：$1 \le N \le 10^5, \; 1 \le Q \le 5 \times 10^5$。
算法分析
考虑点分治，构造一棵重心树。为了方便，下面所有距离均表示在原树上的距离，堆均为大根堆。
设节点$i$在重心树上的父亲为$p_i$。对于每个节点$u$维护两个堆，第一个堆用来维护重心树上$u$子树中的所有黑点到$p_u$的距离，第二个堆用来维护重心树上$u$各个子树中距离$u$最远的黑点到$u$的距离。那么第二个堆可以借助第一个堆来维护。
接着需要一个全局的堆，用来维护所有节点第二个堆的前两个元素之和（经过该点的路径）以及所有黑点第二个堆的第一个元素（以该点为端点的路径）。
修改时，沿着重心树往上依次处理经过的节点，先在全局的堆中删除，再在第二个堆中删除，在第一个堆中修改后，维护第二个堆和全局的堆。
代码
/*
* Computer programmers do it byte by byte.
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
template <typename T> void read(T &n) {
char c;
for (; (c = getchar()) < '0' || c > '9';)
;
for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
;
}
typedef int const ic;
static ic N = 100005;
class heap {
private:
std::priority_queue<int> que, buf;
void clear() {
for (; !que.empty() && !buf.empty() && que.top() == buf.top();
que.pop(), buf.pop())
;
}
public:
void push(ic &n) {
if (n)
que.push(n);
}
void erase(ic &n) {
if (n)
buf.push(n);
}
void pop() {
clear();
if (!que.empty())
que.pop();
}
int top() {
clear();
return que.empty() ? 0 : que.top();
}
int top2() {
clear();
if (que.empty())
return 0;
int tmp = que.top(), ret = tmp;
que.pop(), clear();
if (que.empty()) {
que.push(tmp);
return 0;
}
ret += que.top(), que.push(tmp);
return ret;
}
} global;
namespace tree {
int n, nume, h[N], col[N];
int tim, fi[N], dep[N], lca[N << 1][20];
int power[N << 1];
int root, up[N], size[N], mx[N], vis[N];
heap toup[N], me[N];
struct Edge {
int v, nxt;
} e[N << 1];
void add_edge(ic &u, ic &v) {
e[++nume] = (Edge){v, h[u]}, h[u] = nume;
e[++nume] = (Edge){u, h[v]}, h[v] = nume;
}
void dfs(ic &t, ic &fa) {
lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1;
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa)
dfs(e[i].v, t), lca[++tim][0] = t;
}
void init() {
for (int i = 2; i <= tim; i <<= 1)
++power[i];
for (int i = 1; i <= tim; ++i)
power[i] += power[i - 1];
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= tim; ++j) {
ic k = std::min(tim, j + (1 << i - 1));
lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1]
: lca[k][i - 1];
}
}
int get_lca(ic &u, ic &v) {
ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]);
ic len = power[r - l + 1], k = r - (1 << len) + 1;
return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len];
}
int get_dist(ic &u, ic &v) {
ic lca = get_lca(u, v);
return dep[u] + dep[v] - 2 * dep[lca];
}
int get_size(ic &t, ic &fa) {
int ret = 1;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
ret += get_size(e[i].v, t);
return ret;
}
void get_root(ic &t, ic &fa, ic &tot) {
size[t] = 1, mx[t] = 0;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
get_root(e[i].v, t, tot), size[t] += size[e[i].v],
mx[t] = std::max(mx[t], size[e[i].v]);
(mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t);
}
void init_heap(ic &t, ic &fa, ic &dep, heap &hp) {
hp.push(dep);
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
init_heap(e[i].v, t, dep + 1, hp);
}
void build(int t) {
vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v])
root = 0,
get_root(e[i].v, 0,
size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)),
up[root] = t, init_heap(e[i].v, t, 1, toup[root]),
me[t].push(toup[root].top()), build(root);
global.push(me[t].top()), global.push(me[t].top2());
}
void modify(int t) {
ic p = t;
if (col[t])
global.erase(me[t].top());
else
global.push(me[t].top());
for (; up[t]; t = up[t]) {
if (col[up[t]])
global.erase(me[up[t]].top());
global.erase(me[up[t]].top2());
me[up[t]].erase(toup[t].top());
if (col[p])
toup[t].erase(get_dist(p, up[t]));
else
toup[t].push(get_dist(p, up[t]));
me[up[t]].push(toup[t].top());
if (col[up[t]])
global.push(me[up[t]].top());
global.push(me[up[t]].top2());
}
col[p] = !col[p];
}
} // namespace tree
int main() {
read(tree::n), tree::mx[0] = tree::n;
for (int i = 1, u, v; i < tree::n; ++i)
read(u), read(v), tree::add_edge(u, v);
tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n),
tree::build(tree::root);
for (int i = 1; i <= tree::n; ++i)
tree::col[i] = 1;
int q;
for (read(q); q--;) {
char c;
scanf(" %c", &c);
if (c == 'G')
printf("%d\n", global.top());
else {
int p;
read(p), tree::modify(p);
}
}
return 0;
}