题面
解法
挺恶心的题
考虑动态点分治，先建出点分树
然后每一个点开两个堆，分别为\(a,b\)
\(a_i\)表示点分树上\(i\)子树中所有节点在原树上和点分树中\(i\)父亲的距离，\(b_i\)表示点分树中\(i\)所有儿子的堆顶
再开一个堆\(ans\)，存每一个\(b_i\)最大和次大值的和
在修改的时候，分两种情况考虑
但是本质都是一样的，就是在点分树上不断爬，爬到根为止，然后对当前点和父亲的\(a,b\)进行删除和加入
细节比较多，需要注意
重点：传入一个结构体参数的时候一定要加&，否则会T成皮皮
时间复杂度：\(O(q\ log^2\ n)\)
代码
#include#define inf 1 << 30#define N 100010using namespace std;template void chkmax(node &x, node y) {x = max(x, y);}template void chkmin(node &x, node y) {x = min(x, y);}template void read(node &x) { x = 0; int f = 1; char c = getchar(); while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();} while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;}struct Heap { priority_queue ret, del; void push(int x) {ret.push(x);} void erase(int x) {del.push(x);} int siz() {return ret.size() - del.size();} void Pop() { while (!ret.empty() && !del.empty() && ret.top() == del.top()) ret.pop(), del.pop(); if (ret.size()) ret.pop(); } int top() { if (!siz()) return 0; while (!ret.empty() && !del.empty() && ret.top() == del.top()) ret.pop(), del.pop(); return ret.top(); } int setop() { if (siz() < 2) return 0; int x = top(); Pop(); int y = top(); push(x); return y; }} a[N], b[N], ans;struct Edge { int next, num;} e[N * 3];int n, tot, cnt, rt, now, c[N], d[N], f[N], p[N], dep[N], siz[N], vis[N], ff[N][20];vector E[N];void add(int x, int y) { e[++cnt] = (Edge) {e[x].next, y}; e[x].next = cnt;}void getr(int x, int fa) { f[x] = 0, siz[x] = 1; for (int i = 0; i < E[x].size(); i++) { int k = E[x][i]; if (k == fa || vis[k]) continue; getr(k, x); chkmax(f[x], siz[k]); siz[x] += siz[k]; } chkmax(f[x], now - siz[x]); if (f[x] < f[rt]) rt = x;}void work(int x, int fa) { vis[x] = 1, p[x] = fa; if (fa) add(fa, x); for (int i = 0; i < E[x].size(); i++) { int k = E[x][i]; if (vis[k]) continue; f[rt = 0] = inf, now = siz[k]; getr(k, x); work(rt, x); }}void dfs(int x, int fa) { d[x] = d[fa] + 1; for (int i = 1; i <= 18; i++) ff[x][i] = ff[ff[x][i - 1]][i - 1]; for (int i = 0; i < E[x].size(); i++) { int k = E[x][i]; if (k == fa) continue; ff[k][0] = x; dfs(k, x); }}int lca(int x, int y) { if (d[x] < d[y]) swap(x, y); for (int i = 18; i >= 0; i--) if (d[ff[x][i]] >= d[y]) x = ff[x][i]; if (x == y) return x; for (int i = 18; i >= 0; i--) if (ff[x][i] != ff[y][i]) x = ff[x][i], y = ff[y][i]; return ff[x][0];}int dis(int x, int y) { int z = lca(x, y); return d[x] + d[y] - 2 * d[z];}void update(int x, int y, int z) { a[z].push(dis(x, y)); for (int p = e[x].next; p; p = e[p].next) update(e[p].num, y, z);}void getd(int x) { dep[x] = dep[p[x]] + 1; for (int p = e[x].next; p; p = e[p].next) getd(e[p].num);}void init() { f[rt = 0] = inf; dfs(1, 0); now = n; getr(1, 0); work(rt, 0); for (int i = 1; i <= n; i++) if (p[i]) update(i, p[i], i); for (int i = 1; i <= n; i++) { b[i].push(0); for (int p = e[i].next; p; p = e[p].next) { int k = e[p].num; if (a[k].siz()) b[i].push(a[k].top()); } } for (int i = 1; i <= n; i++) ans.push(b[i].top() + b[i].setop());}void Insert(Heap &a) { if (a.siz() >= 2) { int t = a.top() + a.setop(); ans.push(t); }}void Erase(Heap &a) { if (a.siz() >= 2) { int t = a.top() + a.setop(); ans.erase(t); }}void modify(int x) { if (c[x] == 1) { Erase(b[x]), b[x].push(0); Insert(b[x]); for (int y = x; p[y]; y = p[y]) { Erase(b[p[y]]); if (a[y].siz()) b[p[y]].erase(a[y].top()); a[y].push(dis(p[y], x)); if (a[y].siz()) b[p[y]].push(a[y].top()); Insert(b[p[y]]); } tot++; } else { Erase(b[x]); b[x].erase(0); Insert(b[x]); for (int y = x; p[y]; y = p[y]) { Erase(b[p[y]]); if (a[y].siz()) b[p[y]].erase(a[y].top()); a[y].erase(dis(p[y], x)); if (a[y].siz()) b[p[y]].push(a[y].top()); Insert(b[p[y]]); } tot--; } c[x] ^= 1;}int main() { read(n); cnt = tot = n; for (int i = 1; i < n; i++) { int x, y; read(x), read(y); E[x].push_back(y), E[y].push_back(x); } init(); int q; read(q); while (q--) { char c = getchar(); while (!isalpha(c)) c = getchar(); if (c == 'C') { int x; read(x); modify(x); } else if (tot < 2) cout << tot - 1 << "\n"; else cout << ans.top() << "\n"; } return 0;}