宽广图 题解

思路

记原树中顶点 $v$ 的离心率为

$$e(v)=\max_u \operatorname{dist}(u,v).$$

先考虑阈值为 $k$ 的新图。若 $e(v)<k$，则 $v$ 到任意其他顶点的距离都小于 $k$，所以它在新图中是孤立点。

反过来，树中离心率至少为 $k$ 的所有顶点会处在同一个连通块中。取树直径的两个端点 $A,B$。对任意顶点 $v$，都有

$$e(v)=\max(\operatorname{dist}(v,A),\operatorname{dist}(v,B)).$$

若 $e(v)\ge k$，则 $v$ 至少与 $A,B$ 中的一个相距不少于 $k$。当树的直径不少于 $k$ 时，$A$ 与 $B$ 之间也有边，因此这些非孤立点通过直径端点连成一个连通块。

于是，当 $k$ 不超过树的直径时，答案等于离心率小于 $k$ 的顶点数再加一；当 $k$ 大于直径时，所有顶点都是孤立点，答案为 $n$。

这一结论给出了三种真实的算法层级。

做法

子任务 1 可以从每个顶点进行一次搜索，得到任意两点距离。随后对每个 $k$ 显式枚举点对，在距离不少于 $k$ 时用并查集合并，直接数连通块。

子任务 2 仍从每个顶点进行一次搜索，求出每个顶点的离心率。把离心率排序或计数，即可依次得到离心率小于各个 $k$ 的顶点数。

完整做法只需三次树上搜索。先从任意点出发找到最远点 $A$，再从 $A$ 出发找到最远点 $B$，则 $A,B$ 是一对直径端点。分别求出所有顶点到 $A,B$ 的距离，其较大值就是该顶点的离心率。统计每种离心率的出现次数并做前缀累加，即可输出所有答案。

复杂度

子任务 1 的时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。

子任务 2 的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

完整做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。