题目内容

县域急救路网是一棵 $n$ 个节点的无向带权树，道路 $(u,v)$ 的通行时间为正整数 $w_{uv}$。网上已经建成 $m$ 个互不相同的急救站。调度规程还给出整数 $K$（$1 \le K \le m$）：对每个路口 $v$，把 $v$ 到所有急救站的带权距离从小到大排序，取前 $K$ 个记为 $d_1(v) \le \cdots \le d_K(v)$，定义覆盖指标 $F(v) = \sum_{i=1}^{K} d_i(v)$。

请对每个路口计算 $F(v)$，供值班表评估就近支援能力。

约束：$2 \le m \le n \le 200000$，$1 \le K \le \min(10^2,m)$，边权不超过 1000000。

输入描述

第一行三个整数 $n,m,K$，分别表示节点数、急救站数和 $K$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写