P10092 [ROIR 2022] 网络系统升级计划 (Day 2)

翻译自 [ROIR 2022 D2T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。 某国有 $n$ 个城市，从 $1$ 到 $n$ 编号，首都编号为 $1$。 这个国家的计算机网络构建如下：每个城市都有一个连接中心，可以通过有线通信渠道与其他一些中心相连。对于任意两个城市之间存在着一条唯一的通信路径，换句话说，该网络形成一棵树。对于城市 $i(i > 1)$，我们把从城市 $i$ 到首都的路径上第一个城市记为 $p_i$。 计划对网络进行升级，用更先进的光学通信渠道替换一些现有有线渠道。光学通信渠道只能在现有有线通信渠道的位置上铺设。替换连接城市 $i$ 和 $p_i$ 的通信渠道的成本为 $w_i$。由于技术限制，任何连接中心最多可以直接连接到 $k$ 个其它中心。

通信部希望制定一个升级计划，以提高光学通信渠道的其连通性。因此，需要选择尽可能多的通信渠道进行升级。但是，希望在相同数量的情况下尽量减少升级成本，因此，在相同数量的情况下，选择升级具有最小总成本的通信渠道。 帮助通信部专家选择要升级的通信渠道。

输入的第一行包含两个整数 $n$ 和 $k$。 接下来的 $n−1$ 行描述了通信渠道，其中第 $i−1$ 行包含两个整数：$p_i$ 和 $w_i$（$1 \le p_i < i, 0 \le w_i \le 10^9$）。

输出两个整数 $cnt$ 和 $cost$，表示能够升级的最大通信渠道数量和升级这些通信渠道的最小成本。

样例 $1$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $4$。  样例 $2$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $6$。升级通道的成本显示在边（通信渠道）的旁边，最优解决方案中升级通道的总成本为 $27$。  本题原题分为 $13$ 个 Subtask，但是洛谷不支持设置 $10$ 个以上的 Subtask。本题原题分为 $321$ 个测试点，但是洛谷不支持设置 $100$ 个以上的测试点。所以本题只保留后 $100$ 个测试点，且不使用捆绑测试。 所有数据均满足 $2 \le n \le 10^5, 1 \le k \le 100$。