问题理解

我们有一棵 $n$ 个节点的树，边权为正整数。
需要选择一条长度 $\leq s$ 的路径（称为消防枢纽），使得所有节点到这条路径的距离的最大值最小。
输出这个最小的最大值。

这里“节点到路径的距离”定义为该节点到路径上任意节点的最短距离。

关键性质与观察

1. 最优路径的位置

一个重要结论：最小化最大距离的路径一定在树的直径上。
直观理解：树的直径是树上最长的路径，它能够最好地“覆盖”整棵树。如果最优路径不在直径上，我们可以将其平移至直径上而不增加最大距离。

2. 问题转化

设 $D$ 为我们想要判断的“最大距离”，问题转化为：

• 是否存在一条长度 $\leq s$ 的路径，使得所有节点到该路径的距离 $\leq D$？

这可以用二分答案解决。

二分答案框架

1. 二分可能的答案 $mid$，判断是否存在长度 $\leq s$ 的路径，使得所有节点到路径距离 $\leq mid$。
2. 如果存在，则 $ans \leq mid$，否则 $ans > mid$。

判断函数设计

对于给定的 $D$，如何判断是否存在满足条件的路径？

步骤 1：找出可能覆盖整棵树的路径

一个节点到路径距离 $\leq D$，意味着该节点在路径的 $D$-邻域 内。
因此，我们需要找一条长度 $\leq s$ 的路径，使得其 $D$-邻域覆盖所有节点。

步骤 2：利用直径性质

• 求出树的直径 $U \to V$。
• 最优路径一定在直径 $U \to V$ 上（或可以等效到直径上判断）。
• 在直径上，用**双指针（滑动窗口）**找长度 $\leq s$ 的路径 $[l, r]$。

步骤 3：检查覆盖情况

对于直径上的路径 $[l, r]$，其 $D$-邻域能覆盖所有节点吗？
等价于：所有节点到路径 $[l, r]$ 的距离 $\leq D$。