2025-06-17：移除边之后的权重最大和。用go语言，给定一棵包含 n 个节点（编号 0 到 n-1）的无向树，边的信息由一个长度为 n-1 的数组 edges 提供，其中 edges[i] = [ui, vi, wi] 表示节点 ui 与节点 vi 之间有一条权重为 wi 的边。

你需要选择性地删除一些边（也可以不删），使得满足以下条件：

• o 每个节点最多与 k 个其他节点相连（即每个节点的度不超过 k）。
• o 剩下的边的权重总和尽可能大。

请计算并返回经过边的移除后，剩余边权重和的最大值。

2 <= n <= 100000。

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] <= 1000000。

输入保证 edges 形成一棵有效的树。

输入： 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。

题目来自力扣3367。

详细步骤

1. 构建树的邻接表

首先，我们需要将输入的边转换为邻接表的形式，方便后续的遍历和处理。邻接表是一个数组，每个节点对应一个列表，存储与该节点相连的边（包括连接的节点和边的权重）。

2. 检查简单情况

在开始动态规划之前，可以先检查是否所有节点的度数都不超过 k。如果是，那么不需要删除任何边，直接返回所有边的权重和即可。这样可以避免不必要的计算。

3. 动态规划设计

我们需要设计一个动态规划函数 dfs(x, fa)，其中：

• o x 是当前节点。
• o fa 是当前节点的父节点（避免重复访问）。

函数返回两个值：

• o notChoose：表示不选择父节点与当前节点之间的边时，子树的最大权重和。
• o choose：表示选择父节点与当前节点之间的边时，子树的最大权重和。

4. 动态规划过程

对于当前节点 x，我们需要处理其所有子节点（即邻接表中除父节点外的其他节点）：

1. 1. 初始化：notChoose 和 choose 初始化为 0。
2. 2. 遍历子节点：
3. o 对每个子节点 y，递归调用 dfs(y, x)，得到 nc（不选 x-y 边时的子树和）和 c（选 x-y 边时的子树和）。
4. o 计算增量 d = c + e.wt - nc，即选择 x-y 边比不选时的额外收益。如果 d > 0，则将其加入增量列表 inc。
5. o 累加 notChoose += nc（初始时不选任何子节点的边）。
6. 3. 处理增量：
7. o 对增量列表 inc 进行降序排序。
8. o 对于 choose，可以选择最多 k-1 个增量（因为如果选了父节点的边，当前节点的度数最多为 k，其中父节点占一个，子节点最多 k-1 个）。
9. o 对于 notChoose，可以选择最多 k 个增量（因为不选父节点的边，子节点最多 k 个）。
10. o 分别累加前 k-1 或 k 个增量到 choose 和 notChoose。
11. 4. 返回结果：
12. o notChoose 是不选父节点边时的最大和。
13. o choose 是选父节点边时的最大和。

5. 最终结果

从根节点（如节点 0）开始调用 dfs，返回的 notChoose 就是全局的最大权重和（因为根节点没有父节点，相当于不选父节点边的情况）。

时间复杂度和空间复杂度

• o 时间复杂度：
• o 构建邻接表：O(n)。
• o 动态规划 dfs：每个节点被访问一次，每次访问需要处理其子节点的增量列表。排序增量的总时间是 O(n log n)（因为所有节点的增量列表长度之和是 O(n)，每次排序是 O(m log m)，其中 m 是子节点数量，总排序时间是 O(n log n)）。
• o 总时间复杂度：O(n log n)。
• o 空间复杂度：
• o 邻接表：O(n)。
• o 递归栈：O(n)（最坏情况下树是一条链）。
• o 增量列表：O(n)。
• o 总空间复杂度：O(n)。

总结

通过动态规划和贪心策略（选择增量最大的边），我们可以在 O(n log n) 的时间内解决问题，空间复杂度为 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func maximizeSumOfWeights(edges [][]int, k int)int64 {
    type edge struct{ to, wt int }
    g := make([][]edge, len(edges)+1)
    sumWt := 0
    for _, e := range edges {
        x, y, wt := e[0], e[1], e[2]
        g[x] = append(g[x], edge{y, wt})
        g[y] = append(g[y], edge{x, wt})
        sumWt += wt
    }

    // 优化
    simple := true
    for _, to := range g {
        iflen(to) > k {
            simple = false
            break
        }
    }
    if simple {
        returnint64(sumWt)
    }

    var dfs func(int, int) (int, int)
    dfs = func(x, fa int) (int, int) {
        notChoose := 0
        inc := []int{}
        for _, e := range g[x] {
            y := e.to
            if y == fa {
                continue
            }
            nc, c := dfs(y, x)
            notChoose += nc // 先都不选
            if d := c + e.wt - nc; d > 0 {
                inc = append(inc, d)
            }
        }

        // 再选增量最大的 k 个或者 k-1 个
        slices.SortFunc(inc, func(a, b int)int { return b - a })
        for i := range min(len(inc), k-1) {
            notChoose += inc[i]
        }
        choose := notChoose
        iflen(inc) >= k {
            notChoose += inc[k-1]
        }
        return notChoose, choose
    }
    nc, _ := dfs(0, -1) // notChoose >= choose
    returnint64(nc)
}


func main() {
    edges := [][]int{{0,1,5},{1,2,10},{0,3,15},{3,4,20},{3,5,5},{0,6,10}}
    k := 3
    fmt.Println(maximizeSumOfWeights(edges, k))
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List
from functools import cmp_to_key

def maximizeSumOfWeights(edges: List[List[int]], k: int) -> int:
    n = len(edges) + 1
    g = [[] for _ in range(n)]
    sum_wt = 0
    for x, y, wt in edges:
        g[x].append((y, wt))
        g[y].append((x, wt))
        sum_wt += wt

    # 优化：如果所有节点的度都 <= k，直接返回总权重和
    simple = True
    for neighbors in g:
        if len(neighbors) > k:
            simple = False
            break
    if simple:
        return sum_wt

    def dfs(x: int, fa: int) -> (int, int):
        not_choose = 0
        inc = []
        for y, wt in g[x]:
            if y == fa:
                continue
            nc, c = dfs(y, x)
            not_choose += nc
            d = c + wt - nc
            if d > 0:
                inc.append(d)
        inc.sort(reverse=True)

        # 选增量最大的 k-1 个
        for i in range(min(len(inc), k - 1)):
            not_choose += inc[i]
        choose = not_choose
        if len(inc) >= k:
            not_choose += inc[k-1]
        return not_choose, choose

    nc, _ = dfs(0, -1)
    return nc


if __name__ == "__main__":
    edges = [[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]]
    k = 3
    print(maximizeSumOfWeights(edges, k))

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·