企业官网建设流程全解析

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

题目描述
给定一棵无向树，删除部分边使得每个节点至多与 `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` 个）。

JavaScript 实现

```javascript
/**
* @param {number[][]} edges
* @param {number} k
* @return {number}
*/
var maximizeSumOfWeights = function(edges, k) {
const n = edges.length + 1;

// 构建邻接表
const g = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
g[u].push([v, w]);
g[v].push([u, w]);
}

/**
* DFS 返回: [最多选 k 条边的最大和, 最多选 k-1 条边的最大和]
* @param {number} u - 当前节点
* @param {number} fa - 父节点
* @returns {[number, number]}
*/
const dfs = (u, fa) => {
let s = 0; // 所有子节点都不选边时的基础和
const t = []; // 正收益增量列表

for (const [v, w] of g[u]) {
if (v === fa) continue;

const [a, b] = dfs(v, u); // a = dp_k(v), b = dp_k1(v)
s += a; // 默认不选边 (u,v)

// 选择边 (u,v) 的收益增量
const d = w + b - a;
if (d > 0) {
t.push(d);
}
}

// 按收益降序排序
t.sort((a, b) => b - a);

// 选 k-1 条边（预留一条给父节点）
let sumK1 = s;
for (let i = 0; i < Math.min(t.length, k - 1); i++) {
sumK1 += t[i];
}

// 选 k 条边
let sumK = sumK1;
if (t.length >= k) {
sumK += t[k - 1];
}

return [sumK, sumK1];
};

const [x, y] = dfs(0, -1);
// 根节点没有父节点，两种状态都合法，取最大值
return Math.max(x, y);
};
```

另一种写法（使用优先队列/堆，更简洁）

```javascript
/**
* @param {number[][]} edges
* @param {number} k
* @return {number}
*/
var maximizeSumOfWeights = function(edges, k) {
const n = edges.length + 1;

const g = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
g[u].push([v, w]);
g[v].push([u, w]);
}

const dfs = (u, prev) => {
let weightSum = 0;
const diffs = [];

for (const [v, w] of g[u]) {
if (v === prev) continue;

const [subK1, subK] = dfs(v, u);
weightSum += subK;

// 选择边 (u,v) 的收益增量
diffs.push(Math.max(0, subK1 - subK + w));
}

// 降序排序
diffs.sort((a, b) => b - a);

let topK1 = 0; // 前 k-1 个最大收益
let topK = 0; // 前 k 个最大收益

for (let i = 0; i < k && i < diffs.length; i++) {
if (i < k - 1) topK1 += diffs[i];
topK += diffs[i];
}

return [weightSum + topK1, weightSum + topK];
};

// 返回第二个值（根节点没有父节点，可以用 k 条边）
return dfs(0, -1)[1];
};
```

复杂度分析

指标 复杂度
时间 O(n log n) — 每个节点的子节点收益排序
空间 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. JavaScript 递归深度：`n` 最大为 `10^5`，JavaScript 的递归深度限制通常足够，但如果遇到栈溢出，可以考虑用显式栈模拟 DFS。

验证示例

示例 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