{"problem":{"name":"[ROIR 2022] 网络系统升级计划 (Day 2)","description":{"content":"通信部希望制定一个升级计划，以提高光学通信渠道的其连通性。因此，需要选择尽可能多的通信渠道进行升级。但是，希望在相同数量的情况下尽量减少升级成本，因此，在相同数量的情况下，选择升级具有最小总成本的通信渠道。 帮助通信部专家选择要升级的通信渠道。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10092"},"statements":[{"statement_type":"Markdown","content":"通信部希望制定一个升级计划，以提高光学通信渠道的其连通性。因此，需要选择尽可能多的通信渠道进行升级。但是，希望在相同数量的情况下尽量减少升级成本，因此，在相同数量的情况下，选择升级具有最小总成本的通信渠道。\n\n帮助通信部专家选择要升级的通信渠道。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $k$。\n\n接下来的 $n−1$ 行描述了通信渠道，其中第 $i−1$ 行包含两个整数：$p_i$ 和 $w_i$（$1 \\le p_i < i, 0 \\le w_i \\le 10^9$）。\n\n## Output\n\n输出两个整数 $cnt$ 和 $cost$，表示能够升级的最大通信渠道数量和升级这些通信渠道的最小成本。\n\n[samples]\n\n## Background\n\n翻译自 [ROIR 2022 D2T3](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。\n\n某国有 $n$ 个城市，从 $1$ 到 $n$ 编号，首都编号为 $1$。\n\n这个国家的计算机网络构建如下：每个城市都有一个连接中心，可以通过有线通信渠道与其他一些中心相连。对于任意两个城市之间存在着一条唯一的通信路径，换句话说，该网络形成一棵树。对于城市 $i(i > 1)$，我们把从城市 $i$ 到首都的路径上第一个城市记为 $p_i$。\n\n计划对网络进行升级，用更先进的光学通信渠道替换一些现有有线渠道。光学通信渠道只能在现有有线通信渠道的位置上铺设。替换连接城市 $i$ 和 $p_i$ 的通信渠道的成本为 $w_i$。由于技术限制，任何连接中心最多可以直接连接到 $k$ 个其它中心。\n\n## Note\n\n样例 $1$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $4$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wd46yiot.png)\n\n样例 $2$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $6$。升级通道的成本显示在边（通信渠道）的旁边，最优解决方案中升级通道的总成本为 $27$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/z2mnb3ul.png)\n\n本题原题分为 $13$ 个 Subtask，但是洛谷不支持设置 $10$ 个以上的 Subtask。本题原题分为 $321$ 个测试点，但是洛谷不支持设置 $100$ 个以上的测试点。所以本题只保留后 $100$ 个测试点，且不使用捆绑测试。\n\n所有数据均满足 $2 \\le n \\le 10^5, 1 \\le k \\le 100$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10092","tags":["2022","Special Judge","ROIR（俄罗斯）"],"sample_group":[["8 2\n1 0\n1 0\n1 0\n2 0\n2 0\n2 0\n1 0","4 0"],["8 3\n1 5\n1 2\n1 4\n2 6\n2 7\n2 2\n1 6","6 27"]],"created_at":"2026-03-03 11:09:25"}}