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

最小直径生成树模板。

众所周知，边权全为正的树的所有直径中点重合（有可能在一条边上）。直径问题经常考虑这个点。对于一棵树，设点 $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)$。