动态点分治
先建出点分树，每个点上维护两个堆，s1,s2,分别表示子树中到点分树中父亲的所有长度，每个儿子s1的最大值，那么对于每个点答案就是s2的最大+次大，再维护一个s3保存这个。
首先我们要搞一个带删除的堆，那么我们开两个堆就行了，一个保存元素，一个保存被删除的元素，每次一起弹出就行了
然后是为什么要维护三个堆，每个点记录所有儿子的路径不行吗》这里我想了很长时间，其实很简单，因为记录路径的话有可能最大和次大都是从一个儿子里来的。
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int rd() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int n, sum, m, root; int size[N], f[N], vis[N], val[N], dep[N], fa[N][19], Fa[N]; vector<int> G[N]; struct Heap { priority_queue<int> A, B; void push(int x) { A.push(x); } void del(int x) { B.push(x); } int top() { while(!A.empty() && !B.empty() && A.top() == B.top()) A.pop(), B.pop(); return A.top(); } int sum() { int x = top(); A.pop(); int y = top(); A.push(x); return x + y; } int size() { return A.size() - B.size(); } } s1[N], s2[N], s3; void erase(Heap &s) { if(s.size() > 1) s3.del(s.sum()); } void Insert(Heap &s) { if(s.size() > 1) s3.push(s.sum()); } void dfs(int u, int last) { for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == last) continue; fa[v][0] = u; dep[v] = dep[u] + 1; dfs(v, u); } } int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); int d = dep[u] - dep[v]; for(int i = 18; i >= 0; --i) if(d & (1 << i)) u = fa[u][i]; if(u == v) return u; for(int i = 18; i >= 0; --i) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0]; } int getsize(int u, int last) { int ret = 1; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == last || vis[v]) continue; ret += getsize(v, u); } return ret; } void getroot(int u, int last, int S) { f[u] = 0; size[u] = 1; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == last || vis[v]) continue; getroot(v, u, S); size[u] += size[v]; f[u] = max(f[u], size[v]); } f[u] = max(f[u], S - size[u]); if(f[u] < f[root]) root = u; } void divide(int u) { vis[u] = 1; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(vis[v]) continue; root = 0; getroot(v, u, getsize(v, u)); Fa[root] = u; divide(root); } } int dis(int u, int v) { int x = lca(u, v); return dep[u] + dep[v] - 2 * dep[x]; } void join(int u) { int tmp = u; erase(s2[u]); s2[u].push(0); Insert(s2[u]); while(Fa[u]) { erase(s2[Fa[u]]); if(s1[u].size()) s2[Fa[u]].del(s1[u].top()); s1[u].push(dis(Fa[u], tmp)); s2[Fa[u]].push(s1[u].top()); Insert(s2[Fa[u]]); u = Fa[u]; } } void remove(int u) { int tmp = u; erase(s2[u]); s2[u].del(0); Insert(s2[u]); while(Fa[u]) { erase(s2[Fa[u]]); s2[Fa[u]].del(s1[u].top()); s1[u].del(dis(tmp, Fa[u])); if(s1[u].size()) s2[Fa[u]].push(s1[u].top()); Insert(s2[Fa[u]]); u = Fa[u]; } } int main() { f[0] = 1e9; n = sum = rd(); for(int i = 1; i < n; ++i) { int u = rd(), v = rd(); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); for(int j = 1; j <= 18; ++j) for(int i = 1; i <= n; ++i) fa[i][j] = fa[fa[i][j - 1]][j - 1]; getroot(1, 0, getsize(1, 0)); divide(root); m = rd(); for(int i = 1; i <= n; ++i) join(i), val[i] = 1; while(m--) { char opt[2]; scanf("%s", opt); if(opt[0] == 'G') { if(sum < 2) printf("%d ", sum - 1); else printf("%d ", s3.top()); } if(opt[0] == 'C') { int u = rd(); if(val[u] == 1) { val[u] = 0; remove(u); --sum; } else { val[u] = 1; join(u); ++sum; } } } return 0; }