P15472 [ICPC 2024 WF] Steppe on It 草原上的加速

3s 2048MB 翻译来源：loj #6979. [「ICPC World Finals 2024」草原上的加速](https://loj.ac/p/6979)。

脚踩油门，轮胎尖叫，警笛长鸣。紧急车辆会不惜一切代价以最快的速度到达目标地点。时间至关重要，因为往往关乎生命。 提供紧急服务始终是一个挑战，特别是在像哈萨克草原这样人口稀疏的地区。相比所服务的少量人口，建设基础设施的成本非常高。因此，尽量减少道路数量和车辆数量非常重要。另一方面，尽可能缩短紧急服务的响应时间也是至关重要的。 本题考虑一个已经将道路数量最小化的路网，这意味着任意两个村庄之间有且仅有一条路径相连。多亏了政![]()府拨款，哈萨克草原消防部门最近购置了一些崭新的消防车。该部门希望在一些村庄建立消防站，并将消防车分配到这些消防站，以优化保证的响应时间。 你的任务是找到一个最优的消防车放置方案，使任何村庄都能在最短的时间内被消防车到达。你可以忽略召集消防队员和启动消防车所需的时间，以及穿越村庄所需的时间。响应时间仅由沿道路行驶的时间决定。

第一行包含两个整数：村庄数量 $n$ $(1 \leq n \leq 100\,000)$ 和消防车数量 $f$ $(1 \leq f \leq n)$。 接下来有 $n-1$ 行，编号从 $2$ 到 $n$。第 $i$ 行包含两个整数 $v_{i}$ $(1 \leq v_{i} < i)$ 和 $t_{i}$ $(1 \leq t_{i} \leq 10\,000)$，表示村庄 $i$ 和村庄 $v_{i}$ 之间有一条双向道路，行驶时间为 $t_{i}$。

输出通过将消防车放置在 $f$ 个村庄中可以保证的最小响应时间。