题目大意：有一棵$n(n\leqslant10^6)$个点的树，上面所有点是黑点，有$m$次操作：
- $C\;u$：把点$u$颜色翻转
- $G$：问树上最远的两个黑点的距离，若没有黑点输出$0$
题解：有两个点集，已知它们的直径的端点，可以很快求出点集的并的直径。所有可以用线段树维护所有点的直径。
卡点：考试时没想到
C++ Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
const int maxn = 1e5 + 10, inf = 0x3f3f3f3f; int head[maxn], cnt;
struct Edge {
int to, nxt;
} e[maxn << 1];
inline void addedge(int a, int b) {
e[++cnt] = (Edge) { b, head[a] }; head[a] = cnt;
e[++cnt] = (Edge) { a, head[b] }; head[b] = cnt;
} int n, m;
int Col[maxn]; int dep[maxn], idx;
int LG[maxn << 1], pos[maxn], st[22][maxn << 1], tot;
inline int _min(int a, int b) { return dep[a] < dep[b] ? a : b; }
inline int _max(int a, int b) { return dep[a] > dep[b] ? a : b; }
void dfs(int u, int fa = 0) {
st[0][++tot] = u, pos[u] = tot;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v != fa) {
dep[v] = dep[u] + 1;
dfs(v, u);
st[0][++tot] = u;
}
}
}
inline int LCA(int x, int y) {
static int l, r, len; l = pos[x], r = pos[y];
if (l > r) std::swap(l, r);
len = LG[r - l + 1];
return _min(st[len][l], st[len][r - (1 << len) + 1]);
}
inline int dis(int x, int y) {
return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
} struct Line {
int l, r;
Line() { }
Line(int _l, int _r) : l(_l), r(_r) { }
inline friend bool operator ! (const Line &rhs) {
return !rhs.l && !rhs.r;
}
inline Line operator + (const Line rhs) const {
if (!*this) return rhs;
if (!rhs) return *this;
const int x = rhs.l, y = rhs.r;
int now = dis(l, r), t; Line ans(l, r);
t = dis(l, x); if (now < t) now = t, ans = Line(l, x);
t = dis(l, y); if (now < t) now = t, ans = Line(l, y);
t = dis(r, x); if (now < t) now = t, ans = Line(r, x);
t = dis(r, y); if (now < t) now = t, ans = Line(r, y);
t = dis(x, y); if (now < t) now = t, ans = Line(x, y);
return ans;
}
} ;
namespace SgT {
Line V[maxn << 2];
void modify(int rt, int l, int r, int p, int v) {
if (l == r) {
V[rt] = Line(v, v);
return ;
}
const int mid = l + r >> 1;
if (p <= mid) modify(rt << 1, l, mid, p, v);
else modify(rt << 1 | 1, mid + 1, r, p, v);
V[rt] = V[rt << 1] + V[rt << 1 | 1];
}
int query() {
return dis(V[1].l, V[1].r);
}
} int num;
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n; num = n;
for (int i = 1, a, b; i < n; ++i) {
std::cin >> a >> b;
addedge(a, b);
}
dfs(1); LG[0] = -1;
for (int i = 1; i <= tot; ++i) LG[i] = LG[i >> 1] + 1;
for (int i = 1; i <= LG[tot]; ++i)
for (int j = 1, len = 1 << i; j + len - 1 <= tot; ++j)
st[i][j] = _min(st[i - 1][j], st[i - 1][j + (len >> 1)]);
for (int i = 1; i <= n; ++i) SgT::modify(1, 1, n, i, i);
std::cin >> m;
while (m --> 0) {
char op;
std::cin >> op;
if (op == 'C') {
static int x;
std::cin >> x;
Col[x] ^= 1;
if (Col[x]) SgT::modify(1, 1, n, x, 0), --num;
else SgT::modify(1, 1, n, x, x), ++num;
} else {
if (!num) std::cout << "-1\n";
else std::cout << SgT::query() << '\n';
}
}
return 0;
}