[SDOI2011]消防

题意

一棵树，有边权。选择一条长度不超过 $s$ 的路径，使得所有点到路径的距离最大值最小。

$n\le 3\times 10^5$

题解

算法1

大力猜结论可知，这条路径一定在树上。

先证明一些性质（设 $d_{x,y}$ 表示两点间距离，$f(l)$ 为树中所有点到路径 $l$ 的最远距离）：

• 性质一：离一个点最远的点必然是一直径的端点。

证明：用反证法，讨论三种情况即可。

• 性质二：这条路径必与某条直径相交。

证明：反证，假设这样最优的路径 $l_1$ 不在某条直径上，设直径端点为 $x,y$，直径中与 $l_1$ 距离最短的点为 $u$，不妨设 $d_{x,u}\geq d_{y,u}$。设 $l_1$ 中与 $u$ 最近的点为 $v$，显然 $u\not = v$。

由性质一可知，$l_1$ 的点在树中的最远点为 $x$。$u$ 的最远点也为 $x$。

只取 $u$ 这个点成为一条路径 $l_2$，有 $f(l_2)=d_{u,x} < d_{u,x}+d_{u,v}=f(l_1)$。说明 $l_1$ 不为最优路径，与已知矛盾，证毕。

• 性质三：这条路径可以全在某条直径上。

证明：由性质二，这条路径与直径相交，设相交部分为 $l_2$，其两端点为 $a,b$。还是运用反证法：设 $l_1$ 的两端点为 $c,d$， 易证 $f(l_2)\le f(l_1)$ 而得出矛盾。

综上，我们只需考虑路径全在直径上的情况。

将一条直径的所有点找出来，按顺序排成一排，共 $m$ 个，记为 $a_i$。设非直径中的所有点到 $a_i$ 距离最大值为 $f_i$，从直径一端到 $a_i$ 的距离为 $s_i$。

那么以 $a_{i},a_{j}(i\le j)$ 为端点的路径，最大值为 $\max{\max_{i\le k \le j}{f_k},s_m-s_j,s_i}$

随便用个方法（比如单调队列）即可求出最值。

时间复杂度 $O(n)$。

算法2

既然要最大值最小，那么就二分吧。

二分一个值 $mid$，看是否存在一条路径使得到所有点的距离都不超过 $mid$。

树形DP，设 $f_i$ 表示 $i$ 的子树内，以 $i$ 为端点的路径中，子树内所有点到该路径的距离均不超过 $mid$ 时，路径的最短长度。设 $g_i$ 表示子树内，经过 $i$ 的路径中，子树内所有点到该路径的距离均不超过 $mid$ 时，路径的最短长度。

随便DP一下就可以了。

时间复杂度 $O(n\log n)$，常数略大。