题干与适用场景
这是进阶编程题，考察树分解、距离预处理和动态查询。树有 n 个节点与 n-1 条边，操作在线到达；初始只有一个节点为黑色，之后可任意翻转。查询必须返回当前最近黑点距离，不能为每次查询重新遍历整棵树。
面试官考察什么
- 能否先给出朴素基线，再识别重复遍历的瓶颈。
- 能否证明每个节点到根重心链的长度是对数级，并正确维护链上距离。
- 能否处理重心分解时的子树排除、重复计数、初始无黑点与整数上界。
- 能否比较点分治与多源 BFS、重链剖分、固定黑点场景的适用条件。
回答前需要澄清的问题
需要确认树是否静态、边权是否全为一、操作是否在线、查询是否只要最小距离还是还要返回节点编号，以及是否允许离线重排。若边权为正数，点分治仍可用但距离改为加权和；若树会改边，静态分解不再直接适用。
30 秒回答框架
我会先说明朴素方案每次从 u BFS，最坏是线性。然后对树做点分治：每个节点保存它到所有祖先重心的距离；每个重心维护黑点到自己的最小距离。查询沿 u 的重心祖先链取“u 到重心距离加该重心最小黑点距离”的最小值，更新只需沿同一条链更新堆或集合。重心链长度是对数级，所以每次操作是对数级，预处理是线性对数级。
分步骤深入解答
1. 建立朴素基线与瓶颈
每次 query 从 u 做 BFS 可以得到正确答案，但一次查询会访问大量节点；反复 update 后无法复用“哪些黑点离 u 近”的结构。全局多源 BFS 只适合黑点批量变化，不适合在线翻转。
2. 选择重心并建立祖先链
在当前连通分量中找重心，使删除它后每个子分量规模不超过原分量的一半。递归处理各子分量，形成一棵重心树。原树节点 u 在重心树上有一条祖先链；预处理每个链节点对 (centroid, distance)。每层规模至少减半，因此链长不超过对数级。
3. 维护更新与查询不变量
对每个重心 c，维护所有当前黑节点 v 的 dist(v,c) 最小值。可以用最小堆加懒删除，或用 multiset 支持插入与删除。update(u) 沿 u 的重心祖先链，把 dist(u,c) 加入或删除。query(u) 对同一条链计算 dist(u,c) + best[c] 的最小值。任意路径 u 到黑点 v 会在某一层经过共同重心，因此该组合覆盖了最优路径；每个重心只负责候选，不会漏解。
4. 处理重复计数与堆删除
若使用两个堆，加入操作写入 live 堆，删除操作写入 dead 堆；读取堆顶前不断弹出两堆相等的值。若边权可能相同，堆中应存距离和节点编号，按二元组懒删除，避免只比较距离导致误删。初始黑点应先执行一次 update，查询无黑点时返回约定的无穷大。
5. 复杂度与替代方案
点分治预处理需要遍历每层分量，总复杂度为 O(n log n)，空间为 O(n log n)；每次 update 与 query 访问对数条链，堆操作再乘一个对数因子。若黑点只增加不删除，可用单堆且实现更简单；若查询是固定路径聚合，重链剖分和线段树更自然；若所有操作离线，可考虑按时间分治。
6. C++ 实现骨架
下面代码展示单位边权、黑点翻转和最短距离查询。为避免递归栈过深，生产实现可把找重心的遍历改为显式栈；示例保留递归结构以突出不变量。
#include <bits/stdc++.h>
using namespace std;
struct Entry { int d, u; bool operator>(const Entry& o) const { return tie(d,u) > tie(o.d,o.u); } };
int n;
vector<vector<int>> g;
vector<int> sub, dead, black;
vector<vector<pair<int,int>>> chain;
vector<priority_queue<Entry, vector<Entry>, greater<Entry>>> liveHeap, deadHeap;
void calcSize(int u, int p) {
sub[u] = 1;
for (int v : g[u]) if (v != p && !dead[v]) { calcSize(v,u); sub[u] += sub[v]; }
}
int findCentroid(int u, int p, int total) {
for (int v : g[u]) if (v != p && !dead[v] && sub[v] > total/2)
return findCentroid(v,u,total);
return u;
}
void collect(int u, int p, int c, int d) {
chain[u].push_back({c,d});
for (int v : g[u]) if (v != p && !dead[v]) collect(v,u,c,d+1);
}
void decompose(int entry) {
calcSize(entry,-1);
int c = findCentroid(entry,-1,sub[entry]);
dead[c] = 1;
collect(c,-1,c,0);
for (int v : g[c]) if (!dead[v]) decompose(v);
}
void clean(int c) {
while (!liveHeap[c].empty() && !deadHeap[c].empty() &&
liveHeap[c].top().d == deadHeap[c].top().d &&
liveHeap[c].top().u == deadHeap[c].top().u) {
liveHeap[c].pop(); deadHeap[c].pop();
}
}
void update(int u) {
black[u] ^= 1;
for (auto [c,d] : chain[u]) {
if (black[u]) liveHeap[c].push({d,u});
else deadHeap[c].push({d,u});
}
}
int query(int u) {
const int INF = 1e9; int ans = INF;
for (auto [c,d] : chain[u]) { clean(c); if (!liveHeap[c].empty()) ans = min(ans, d + liveHeap[c].top().d); }
return ans == INF ? -1 : ans;
}高质量示范回答
我会用点分治把静态树变成重心树。预处理时，为每个节点记录到每个重心祖先的距离；每个重心维护当前黑点到它的最小距离。翻转节点时沿祖先链插入或懒删除距离，查询时取所有祖先的“到重心距离加重心最小黑点距离”的最小值。路径在某层一定经过共同重心，所以最优黑点不会被漏掉。重心链是对数长度，预处理约为 O(n log n)；使用堆懒删除时更新和查询为对数链长乘堆操作开销。若只有新增没有删除，我会去掉删除堆；若树边会动态改变，则改用支持动态树的结构。
常见错误
- 每次查询 BFS → 正确但无法承受大量在线操作 → 先给基线，再引入重心链。
- 只把节点加入最近重心 → 路径可能经过更高层重心 → 为每个节点保存完整祖先链。
- 懒删除只比较距离 → 相同距离的不同节点会误删 → 堆项同时记录节点编号。
- 把重心分解误当成 LCA → 两者解决的问题不同 → 明确这里维护的是动态集合到单点距离。
- 忽略初始无黑点 → 返回未初始化的大数 → 约定返回
-1并在框架中说清楚。
追问及应对
如果边有正权，算法要怎么改？
收集祖先链时累计边权而非步数，堆里保存加权距离；重心分解依据节点数仍成立。若允许零或正权，最小值不变量不变。
如果还要返回最近黑点的编号呢？
堆项保存 (distance, nodeId) 并按字典序比较。多个黑点同距时可按编号稳定选取；查询组合时同时维护当前最优距离和编号。
为什么不能只维护 u 的父重心？
最近黑点可能位于与 u 不同的子分量，路径会在更高层重心汇合。只检查一个父重心会漏掉跨分量的最优答案，必须遍历整条祖先链。
什么时候重链剖分更合适？
当操作是路径上的可结合聚合、需要查询任意两点路径，或黑点集合不是“节点到集合的最小距离”时，重链剖分加线段树通常更直接。点分治适合围绕一个节点对动态集合做距离聚合。