Hard

题目描述

存在一个有 n 个节点的无向树，节点编号为 0 到 n - 1。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权重为 wi 的边。

你的任务是删除零条或多条边，使得：

  • 每个节点最多与 k 个其他节点有边相连，其中 k 是给定的。
  • 剩余边的权重和最大化。

返回删除必要的边后剩余边的最大可能权重和。

示例 1：

输入：edges = [[0,1,4],[0,2,2],[2,3,12],[2,4,6]], k = 2
输出：22
解释：
节点 2 与 3 个其他节点有边。我们删除边 [0, 2, 2]，确保没有节点与超过 k = 2 个节点有边。
权重和为 22，我们无法获得更大的和。因此，答案是 22。

示例 2：

输入：edges = [[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]], k = 3
输出：65
解释：
由于没有节点与超过 k = 3 个节点相连，我们不删除任何边。
权重和为 65。因此，答案是 65。

约束条件：

  • 2 <= n <= 10⁵
  • 1 <= k <= n - 1
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= edges[i][0] <= n - 1
  • 0 <= edges[i][1] <= n - 1
  • 1 <= edges[i][2] <= 10⁶
  • 输入保证 edges 形成一个有效的树。

解题思路

这是一个树形动态规划问题。核心思想是通过 DFS 遍历树，对每个节点考虑两种状态：

  1. 状态定义：

    • dp[u][0]：以节点 u 为根的子树中，u 与父节点不连接时的最大权重和
    • dp[u][1]：以节点 u 为根的子树中，u 与父节点连接时的最大权重和

  2. 转移策略：

    • 对于每个节点，收集所有子边的贡献值
    • 贡献值 = dp[child][1] + weight - dp[child][0]（选择连接子节点的额外收益）
    • 将所有贡献值按降序排列，贪心选择最优的前 k 条边（状态0）或前 k-1 条边（状态1）

  3. 贪心选择：

    • 状态0：最多可以选择 k 条边连接子节点
    • 状态1：由于要与父节点连接，最多只能选择 k-1 条边连接子节点
    • 对于每条边，比较连接和不连接的收益，选择正收益的边

  4. 时间复杂度：O(n log n)，主要是排序的开销 空间复杂度：O(n)，递归栈和存储空间

代码实现

class Solution {
public:
    long long maximizeSumOfWeights(vector<vector<int>>& edges, int k) {
        int n = edges.size() + 1;
        vector<vector<pair<int, int>>> adj(n);
        
        for (auto& edge : edges) {
            adj[edge[0]].push_back({edge[1], edge[2]});
            adj[edge[1]].push_back({edge[0], edge[2]});
        }
        
        function<pair<long long, long long>(int, int)> dfs = [&](int u, int parent) -> pair<long long, long long> {
            vector<long long> gains;
            long long base = 0;
            
            for (auto [v, w] : adj[u]) {
                if (v == parent) continue;
                auto [dp0, dp1] = dfs(v, u);
                base += dp0;
                gains.push_back(max(0LL, dp1 + w - dp0));
            }
            
            sort(gains.rbegin(), gains.rend());
            
            long long sum0 = base, sum1 = base;
            for (int i = 0; i < min(k, (int)gains.size()); i++) {
                sum0 += gains[i];
            }
            for (int i = 0; i < min(k-1, (int)gains.size()); i++) {
                sum1 += gains[i];
            }
            
            return {sum0, sum1};
        };
        
        return dfs(0, -1).first;
    }
};

class Solution:
    def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
        n = len(edges) + 1
        adj = [[] for _ in range(n)]
        
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))
        
        def dfs(u, parent):
            gains = []
            base = 0
            
            for v, w in adj[u]:
                if v == parent:
                    continue
                dp0, dp1 = dfs(v, u)
                base += dp0
                gains.append(max(0, dp1 + w - dp0))
            
            gains.sort(reverse=True)
            
            sum0 = base
            sum1 = base
            
            for i in range(min(k, len(gains))):
                sum0 += gains[i]
            
            for i in range(min(k-1, len(gains))):
                sum1 += gains[i]
            
            return sum0, sum1
        
        return dfs(0, -1)[0]

public class Solution {
    public long MaximizeSumOfWeights(int[][] edges, int k) {
        int n = edges.Length + 1;
        var adj = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<(int, int)>();
        }
        
        foreach (var edge in edges) {
            adj[edge[0]].Add((edge[1], edge[2]));
            adj[edge[1]].Add((edge[0], edge[2]));
        }
        
        (long, long) Dfs(int u, int parent) {
            var gains = new List<long>();
            long baseSum = 0;
            
            foreach (var (v, w) in adj[u]) {
                if (v == parent) continue;
                var (dp0, dp1) = Dfs(v, u);
                baseSum += dp0;
                gains.Add(Math.Max(0L, dp1 + w - dp0));
            }
            
            gains.Sort((a, b) => b.CompareTo(a));
            
            long sum0 = baseSum, sum1 = baseSum;
            
            for (int i = 0; i < Math.Min(k, gains.Count); i++) {
                sum0 += gains[i];
            }
            
            for (int i = 0; i < Math.Min(k - 1, gains.Count); i++) {
                sum1 += gains[i];
            }
            
            return (sum0, sum1);
        }
        
        return Dfs(0, -1).Item1;
    }
}

var maximizeSumOfWeights = function(edges, k) {
    const n = edges.length + 1;
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        graph[v].push([u, w]);
    }
    
    function dfs(node, parent) {
        const children = [];
        
        for (const [child, weight] of graph[node]) {
            if (child !== parent) {
                const [inc, exc] = dfs(child, node);
                children.push([inc + weight, exc, weight]);
            }
        }
        
        children.sort((a, b) => (b[0] - b[1]) - (a[0] - a[1]));
        
        let incSum = 0, excSum = 0;
        
        for (let i = 0; i < children.length; i++) {
            const [inc, exc] = children[i];
            if (i < k - 1) {
                incSum += Math.max(inc, exc);
                excSum += Math.max(inc, exc);
            } else if (i === k - 1) {
                incSum += exc;
                excSum += Math.max(inc, exc);
            } else {
                excSum += Math.max(inc, exc);
            }
        }
        
        return [incSum, excSum];
    }
    
    return dfs(0, -1)[1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n log n)
空间复杂度O(n)

解释：

  • 时间复杂度：每个节点访问一次，对每个节点的子边进行排序，总体为 O(n log n)
  • 空间复杂度：递归栈深度最大为 O(n)，邻接表存储为 O(n)

相关题目