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

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^5JavaScript 的递归深度限制通常足够但如果遇到栈溢出可以考虑用显式栈模拟 DFS。验证示例示例 1edges [[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示例 2edges [[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