当前位置：首页 > news >正文

DeepSeek LeetCode 3553. 包含要求路径的最小带权子图 II JavaScript实现

news 2026/7/15 4:43:14

核心思路

本题给定的是无向带权树，树中任意两点间有且仅有一条简单路径。对于每个查询 (src1, src2, dest)，包含两条路径的最小连通子图就是这两条路径的并集。

关键公式：三条路径 (src1→src2)、(src1→dest)、(src2→dest) 的并集总权重为：

```
(dist(src1, src2) + dist(src1, dest) + dist(src2, dest)) / 2
```

因为并集中的每条边在三段两两距离中恰好被计算两次。

预处理使用二进制提升（Binary Lifting）求LCA，单次查询 O(log n)。

完整 JavaScript 实现

```javascript
/**
* @param {number[][]} edges - 边列表 [u, v, w]
* @param {number[][]} queries - 查询列表 [src1, src2, dest]
* @return {number[]} - 每个查询的最小总权重
*/
function minimumWeight(edges, queries) {
const n = edges.length + 1;
const graph = Array.from({ length: n }, () => []);

// 构建无向图
for (const [u, v, w] of edges) {
graph[u].push([v, w]);
graph[v].push([u, w]);
}

// DFS 预处理 parent 和 depth
const parent = Array(n).fill([-1, 0]);
const depth = Array(n).fill(0);

function dfs(node, par, parWeight, d) {
depth[node] = d;
parent[node] = [par, parWeight];
for (const [nei, weight] of graph[node]) {
if (nei === par) continue;
dfs(nei, node, weight, d + 1);
}
}
dfs(0, -1, 0, 0);

const lca = new LCA(n, parent, depth);
const ans = [];

for (const [src1, src2, dest] of queries) {
const d1 = lca.getDist(src1, src2);
const d2 = lca.getDist(src1, dest);
const d3 = lca.getDist(src2, dest);
ans.push((d1 + d2 + d3) / 2);
}

return ans;
}

class LCA {
constructor(n, parent, depth) {
this.maxDepth = Math.ceil(Math.log2(n)) + 1;
this.depth = depth;

// up[k][v] = v 的 2^k 级祖先
this.up = Array.from({ length: this.maxDepth }, () => Array(n).fill(-1));
// sum[k][v] = v 到其 2^k 级祖先的路径权重和
this.sum = Array.from({ length: this.maxDepth }, () => Array(n).fill(0));

// 初始化第 0 层
for (let v = 0; v < n; v++) {
this.up[0][v] = parent[v][0];
this.sum[0][v] = parent[v][1];
}

// 递推计算更高层
for (let k = 1; k < this.maxDepth; k++) {
for (let v = 0; v < n; v++) {
const mid = this.up[k - 1][v];
if (mid !== -1) {
this.up[k][v] = this.up[k - 1][mid];
this.sum[k][v] = this.sum[k - 1][v] + this.sum[k - 1][mid];
}
}
}
}

// 获取 LCA
getLCA(a, b) {
if (this.depth[a] > this.depth[b]) [a, b] = [b, a];

// 将 b 提升到与 a 同深度
let diff = this.depth[b] - this.depth[a];
for (let k = 0; k < this.maxDepth; k++) {
if ((diff >> k) & 1) {
b = this.up[k][b];
}
}

if (a === b) return a;

// 同时提升
for (let k = this.maxDepth - 1; k >= 0; k--) {
if (this.up[k][a] !== this.up[k][b]) {
a = this.up[k][a];
b = this.up[k][b];
}
}

return this.up[0][a];
}

// 获取 a 到 b 的路径权重和
getDist(a, b) {
const lca = this.getLCA(a, b);
return this._getUpSum(a, this.depth[a] - this.depth[lca]) +
this._getUpSum(b, this.depth[b] - this.depth[lca]);
}

// 获取节点 v 到其 k 级祖先的路径权重和（内部方法）
_getUpSum(v, k) {
let sum = 0;
for (let i = 0; i < this.maxDepth; i++) {
if ((k >> i) & 1) {
sum += this.sum[i][v];
v = this.up[i][v];
}
}
return sum;
}
}