企业官网建设流程全解析

LeetCode 3367. 移除边之后的权重最大和 — Python3 实现

题目描述
给定一棵无向树（`n` 个节点，`n-1` 条边），删除部分边使得每个节点至多与 `k` 个其他节点相连，求剩余边权重的最大和。

核心思路（树形 DP + 贪心）

以节点 `0` 为根进行 DFS。对于每个节点 `u`，定义两个状态：

状态 含义
`dp_k` 节点 `u` 最多连接 k 条边 到子节点的最大权重和
`dp_k1` 节点 `u` 最多连接 k-1 条边 到子节点的最大权重和（预留一条给父节点）

对于子节点 `v`，边权为 `w`：
- 不选边 `(u,v)`：子树贡献 `dp_k(v)`
- 选边 `(u,v)`：子树贡献 `w + dp_k1(v)`

选择这条边的收益增量为：`delta = w + dp_k1(v) - dp_k(v)`

对每个节点，收集所有正收益增量，按降序排序，贪心取前 `k` 个（或 `k-1` 个）。

Python3 实现

```python
from typing import List, Tuple

class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
n = len(edges) + 1

# 构建邻接表
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))

def dfs(u: int, fa: int) -> Tuple[int, int]:
"""
返回:
- 第一个值: 节点 u 最多选 k 条边连子节点的最大权重和
- 第二个值: 节点 u 最多选 k-1 条边连子节点的最大权重和（预留一条给父节点）
"""
s = 0 # 所有子节点都不选边时的基础和
t = [] # 正收益增量列表

for v, w in g[u]:
if v == fa:
continue

a, b = dfs(v, u) # a = dp_k(v), b = dp_k1(v)
s += a # 默认不选边 (u,v)

# 选择边 (u,v) 的收益增量
d = w + b - a
if d > 0:
t.append(d)

# 按收益降序排序，贪心选最优的边
t.sort(reverse=True)

# 选 k-1 条边（预留一条给父节点）
sum_k1 = s + sum(t[:k - 1])
# 选 k 条边
sum_k = s + sum(t[:k])

return sum_k, sum_k1

x, y = dfs(0, -1)
# 根节点没有父节点，两种状态都合法，取最大值
return max(x, y)
```

另一种写法（使用 heapq.nlargest）

```python
import heapq
from typing import List, Tuple

class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
n = len(edges) + 1
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))

def dfs(u: int, prev: int) -> Tuple[int, int]:
weight_sum = 0
diffs = []

for v, w in g[u]:
if v == prev:
continue

sub_k1, sub_k = dfs(v, u)
weight_sum += sub_k

# 选择边 (u,v) 的收益增量
diffs.append(max(0, sub_k1 - sub_k + w))

# 取前 k 个 / 前 k-1 个最大收益
return (weight_sum + sum(heapq.nlargest(k, diffs)),
weight_sum + sum(heapq.nlargest(k - 1, diffs)))

return dfs(0, -1)[1]
```

复杂度分析

指标 复杂度
时间 O(n log n) — 每个节点的子节点收益排序（或用 heapq）
空间 O(n) — 邻接表 + 递归栈

关键点说明

1. 收益增量 `delta = w + dp_k1(v) - dp_k(v)`：表示"选择边 `(u,v)` 相比不选"能额外获得的收益。如果为负，则不选更优。

2. 两种状态设计：
- `dp_k`：节点 `u` 可以向子节点连最多 `k` 条边
- `dp_k1`：节点 `u` 只能向子节点连最多 `k-1` 条边，预留一个位置给父节点

3. 根节点处理：根节点没有父节点，所以最终答案取 `max(x, y)` 均可。

4. Python 递归深度：`n` 最大为 `10^5`，Python 默认递归深度限制为 1000，需要在提交时设置 `sys.setrecursionlimit(200000)`。

完整可运行版本（含递归深度设置）

```python
import sys
from typing import List, Tuple

# 提升递归深度限制
sys.setrecursionlimit(200000)

class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
n = len(edges) + 1
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))

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
d = w + b - a
if d > 0:
t.append(d)
t.sort(reverse=True)
return s + sum(t[:k]), s + sum(t[:k - 1])

x, y = dfs(0, -1)
return max(x, y)
```

验证示例

示例 1：`edges = [[0,1,4],[0,2,2],[2,3,12],[2,4,6]], k = 2` → 22

- 节点 2 有 3 条边（连 0,3,4），需删除一条
- 删除边 `(0,2,2)`（收益最小），保留 `(2,3,12)` 和 `(2,4,6)`
- 加上 `(0,1,4)`，总和 = 4 + 12 + 6 = 22

示例 2：`edges = [[0,1,5],[1,2,10],[0,3,15],[3,4,20],[3,5,5],[0,6,10]], k = 3` → 65

- 没有节点超过 3 条边，全部保留
- 总和 = 5 + 10 + 15 + 20 + 5 + 10 = 65