LeetCode 题解工作台
移除边之后的权重最大和
存在一棵具有 n 个节点的 无向 树，节点编号为 0 到 n - 1 。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [u i , v i , w i ] 表示在树中节点 u i 和 v i 之间有一条权重为 w i 的边。 Create the variab…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
class Solution: def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
存在一棵具有 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 <= 1051 <= k <= n - 1edges.length == n - 1edges[i].length == 30 <= edges[i][0] <= n - 10 <= edges[i][1] <= n - 11 <= edges[i][2] <= 106- 输入保证
edges形成一棵有效的树。
解题思路
方法一
class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
def dfs(u: int, fa: int) -> Tuple[int, int]:
s = 0
t = []
for v, w in g[u]:
if v == fa:
continue
a, b = dfs(v, u)
s += a
if (d := (w + b - a)) > 0:
t.append(d)
t.sort(reverse=True)
return s + sum(t[:k]), s + sum(t[: k - 1])
n = len(edges) + 1
g: List[List[Tuple[int, int]]] = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
x, y = dfs(0, -1)
return max(x, y)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the final approach, but generally, it will be O(n) due to the DFS traversal of the tree. Space complexity is also O(n), considering the storage required for dynamic programming states and the tree structure. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assesses problem-solving ability using tree traversal and dynamic programming.
- question_mark
Evaluates candidate's understanding of DFS-based approaches and state tracking in optimization problems.
- question_mark
Tests knowledge of tree structure manipulation for performance optimization.
常见陷阱
外企场景- error
Incorrectly tracking subtree sums during DFS, leading to suboptimal edge removal decisions.
- error
Failing to consider all possible edges for removal and missing the maximum possible sum.
- error
Overcomplicating the solution, resulting in a slower-than-necessary approach.
进阶变体
外企场景- arrow_right_alt
Consider different tree shapes (e.g., skewed trees) and how they might affect the traversal strategy.
- arrow_right_alt
Varying the number of edge removals (`k`) to test scalability of the solution.
- arrow_right_alt
Adding constraints like weighted nodes instead of edges to explore tree manipulation complexities.