题目内容

给定一棵包含 $n$ 个节点的无向带权树，每条边 $(u, v)$ 的权重为正整数 $w_{uv}$。树上共有 $m$ 个标记为"红点"的节点。给定一个整数 $K (1 ≤ K ≤ m)$ ，对于每个节点 $v$ ，定义该节点到树中 $K$ 个最近红点的距离和：$F(v) = \sum_{i=1}^{K}$ $d_i(v)$ 其中 $d_1(v) ≤ d_2(v) ≤ … ≤ d_K(v)$ 是节点 $v$ 到所有红点按距离从小到大排序的前 $K$ 个距离。请计算所有节点的 $F(v)$ 。

输入描述

第一行输入三个整数 $n, m, K (2 ≤ m ≤ n ≤ 2 × 10^5, 1 ≤ K ≤ min(100, m))$ , 分别表示节点数、红点数和 $K$ 。

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