核心思路
本题给定的是无向带权树，树中任意两点间有且仅有一条简单路径。对于每个查询 (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;
}
}
// 测试用例
console.log(minimumWeight(
[[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]],
[[2,3,4],[0,2,5]]
)); // [12, 11]
console.log(minimumWeight(
[[1,0,8],[0,2,7]],
[[0,1,2]]
)); // [15]
```
复杂度分析
项目 复杂度
预处理（DFS + 二进制表） O(n log n)
单次查询 O(log n)
空间 O(n log n)
其中 n 为节点数，m 为查询数。
