P2491 [SDOI2011] 消防

某个国家有 $n$ 个城市，这 $n$ 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 $z_i$。 这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。 现在这个国家的经费足以在一条边长度和不超过 $s$ 的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。 你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

无

无

对于 $20\%$ 的数据，$n \le 300$。 对于 $50\%$ 的数据，$n \le 3 \times 10^3$。 对于 $100\%$ 的数据，$1\le n \le 3 \times 10^5$，$1\le z_i \le 10^3$。 - 注意，数据中存在权值为 $0$ 的边。 ------------ 2024/1/28 添加一组 hack 数据。