题解：P14620 [2019 KAIST RUN Fall] Minimum Diameter Spanning Tree

complexor · 2025-11-28 20:43:04 · 题解

最小直径生成树模板。

众所周知，边权全为正的树的所有直径中点重合（有可能在一条边上）。直径问题经常考虑这个点。对于一棵树，设点 x 到直径中点的距离为 d_x，直径为 D，则 D=2\max_x{d_x}。进一步，如果将 d_x 改为 x 到任一其他点（包括一条边中间），这个等式右侧都会变大。

回到原题，如果已经求出最小直径生成树的直径中点 C（如果在边上就在边中间插一个点），那么求出以 C 为起点的最短路树即为最小直径生成树。

先通过 Floyd 算法求出全源最短路，记为 d(u,v)。枚举答案的直径中点 C 在边 (u,v,w) 上，考虑将剩下的 n-2 个点划分为点集 U,V，让 U 中的点都经过 u 到 C，V 中的点都经过 v 到 C。设 L=\max_{x\in U}(d(u,x))，R=\max_{x\in V}(d(v,x))。那么此时 C 到所有点最短路的最大值即为 \max\{L,R,\frac{L+R+w}{2}\}。考虑枚举 L=d(u,x)，则可以贪心地取 U=\{y|d(u,y)\leq L\}，V 为剩下的点。也就是将所有点按照到 u 的距离排序，U 依次取每个前缀，V 分别取剩下的后缀即可。

排序只需要对每个点各做一次，复杂度为 O(n^2\log n)，全源最短路和枚举 U,V 复杂度均为 O(n^3)。

注意到当答案的 C 确实在 (u,v) 上并且 \max\{L,R,\frac{L+R+w}{2}\}=D 时，必然有 |L-R|\leq w，此时 C 为边 (u,v) 上与 u 距离为 \frac{R+w-L}{2} 的点，所以构造是容易的。

总复杂度 O(n^3)。