问题分析

这道题要求我们在树形结构的城市网络中，选择尽可能多的有线通信渠道升级为光纤渠道，同时要满足每个连接中心最多只能通过光纤渠道连接到 $k$ 个其他中心的限制。在最大化升级数量的前提下，还需要最小化总成本。

这是一个典型的树形动态规划问题，关键在于如何在满足每个节点度约束的情况下，选择最优的边集合进行升级。

算法思路

我们可以采用后序遍历（从叶子到根）的方式处理整棵树，并使用动态规划来记录每个节点的最优选择：

1. 对于每个节点 $u$，我们需要考虑从它的子节点中选择多少条边进行升级
2. 每个节点最多只能选择 $k$ 个子节点的边进行升级
3. 为了最小化成本，我们应该优先选择成本较低的边

具体来说，对于每个节点 $u$：

• 收集所有子节点 $v$ 升级边 $(v, u)$ 后能获得的最大数量和对应成本
• 按照"单位数量的成本"排序（实际上是比较两个选择的性价比）
• 选择前 $min(k, 子节点数)$ 个最优的子节点边进行升级
• 记录当前节点的最大升级数量和最小成本

实现代码

import sys
from functools import cmp_to_key

def main():
    sys.setrecursionlimit(1 << 25)
    n, k = map(int, sys.stdin.readline().split())
    
    # 构建树，children[u] 存储 u 的子节点列表 (节点, 权重)
    children = [[] for _ in range(n + 1)]
    for v in range(2, n + 1):
        p, w = map(int, sys.stdin.readline().split())
        children[p].append((v, w))
    
    # 后序遍历处理树
    def post_order(u):
        # 存储每个子节点的 (最大数量, 最小成本)
        options = []
        
        for v, w in children[u]:
            cnt, cost = post_order(v)
            # 如果选择升级这条边，总数量+1，总成本+w
            options.append((cnt + 1, cost + w))
        
        # 排序函数：优先选择数量多的；数量相同则选择成本低的
        def compare(a, b):
            if a[0] != b[0]:
                return b[0] - a[0]  # 数量降序
            return a[1] - b[1]      # 成本升序
        
        options.sort(key=cmp_to_key(compare))
        
        # 最多选择 k 个子节点
        take = min(k, len(options))
        total_cnt = 0
        total_cost = 0
        
        for i in range(take):
            total_cnt += options[i][0]
            total_cost += options[i][1]
        
        return total_cnt, total_cost
    
    cnt, cost = post_order(1)
    print(cnt, cost)

if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度：$O(nk \log k)$，其中 $n$ 是节点数量，$k$ 是每个节点最多能连接的光纤数。对于每个节点，我们需要对其子节点进行排序，排序的时间复杂度为 $O(k \log k)$。
• 空间复杂度：$O(n)$，主要用于存储树结构和递归调用栈。

算法标签

• 树形动态规划
• 分组背包问题
• 贪心策略
• 树的后序遍历
• 状态压缩优化

算法正确性说明

算法通过后序遍历确保了我们先处理完所有子节点，再处理父节点，这符合动态规划的最优子结构性质。

对于每个节点，我们选择能带来最大升级数量的子节点边，在数量相同的情况下选择成本最低的，这保证了：

1. 最大化升级的总数量
2. 在数量相同的情况下最小化总成本
3. 满足每个节点最多连接 $k$ 个光纤渠道的约束

因此，该算法能够得到题目要求的最优解。