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

Luogu
IDLGP10092
Time1000ms
Memory256MB
DifficultyP4
2022Special JudgeROIR(俄罗斯)
通信部希望制定一个升级计划,以提高光学通信渠道的其连通性。因此,需要选择尽可能多的通信渠道进行升级。但是,希望在相同数量的情况下尽量减少升级成本,因此,在相同数量的情况下,选择升级具有最小总成本的通信渠道。 帮助通信部专家选择要升级的通信渠道。 ## Input 输入的第一行包含两个整数 $n$ 和 $k$。 接下来的 $n−1$ 行描述了通信渠道,其中第 $i−1$ 行包含两个整数:$p_i$ 和 $w_i$($1 \le p_i < i, 0 \le w_i \le 10^9$)。 ## Output 输出两个整数 $cnt$ 和 $cost$,表示能够升级的最大通信渠道数量和升级这些通信渠道的最小成本。 [samples] ## Background 翻译自 [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$ 个其它中心。 ## Note 样例 $1$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $4$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/wd46yiot.png) 样例 $2$ 中的网络配置在升级前后如下图所示。需要升级的通信渠道以粗线表示。可以升级的最大通信渠道数量为 $6$。升级通道的成本显示在边(通信渠道)的旁边,最优解决方案中升级通道的总成本为 $27$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/z2mnb3ul.png) 本题原题分为 $13$ 个 Subtask,但是洛谷不支持设置 $10$ 个以上的 Subtask。本题原题分为 $321$ 个测试点,但是洛谷不支持设置 $100$ 个以上的测试点。所以本题只保留后 $100$ 个测试点,且不使用捆绑测试。 所有数据均满足 $2 \le n \le 10^5, 1 \le k \le 100$。
Samples
Input #1
8 2
1 0
1 0
1 0
2 0
2 0
2 0
1 0
Output #1
4 0
Input #2
8 3
1 5
1 2
1 4
2 6
2 7
2 2
1 6
Output #2
6 27
API Response (JSON)
{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments