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

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

• 每个节点最多与 k 个其他节点相连（即每个节点的度不超过 k）。

• 剩下的边的权重总和尽可能大。

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

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)，其中：

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

函数返回两个值：

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

4. 动态规划过程

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

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

5. 最终结果

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

时间复杂度和空间复杂度

• 时间复杂度：
  • 构建邻接表：O(n)。
  • 动态规划 dfs：每个节点被访问一次，每次访问需要处理其子节点的增量列表。排序增量的总时间是 O(n log n)（因为所有节点的增量列表长度之和是 O(n)，每次排序是 O(m log m)，其中 m 是子节点数量，总排序时间是 O(n log n)）。
  • 总时间复杂度：O(n log n)。
• 空间复杂度：
  • 邻接表：O(n)。
  • 递归栈：O(n)（最坏情况下树是一条链）。
  • 增量列表：O(n)。
  • 总空间复杂度：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 {
		if len(to) > k {
			simple = false
			break
		}
	}
	if simple {
		return int64(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
		if len(inc) >= k {
			notChoose += inc[k-1]
		}
		return notChoose, choose
	}
	nc, _ := dfs(0, -1) // notChoose >= choose
	return int64(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))