这是 LeetCode 3553 的 Rust 实现。核心思路是答案 (dist(src1, src2) dist(src1, dest) dist(src2, dest)) / 2即三个点的最小连通子树的边权和等于两两距离之和除以 2。求树上距离需要用到 LCA 倍增。rustuse std::collections::VecDeque;struct Solution;impl Solution {pub fn minimum_weight(edges: VecVeci32, queries: VecVeci32) - Veci32 {let n edges.len() 1;if n 0 {return vec![];}// 建图let mut graph: VecVec(usize, i32) vec![vec![]; n];for e in edges {let u e[0] as usize;let v e[1] as usize;let w e[2];graph[u].push((v, w));graph[v].push((u, w));}// 倍增 LCA 预处理let log_n (n as f64).log2().ceil() as usize 1;let mut up vec![vec![0; log_n]; n]; // up[v][j] 2^j 级祖先let mut depth vec![0; n];let mut dist vec![0i64; n]; // 到根的距离用 i64 防溢出// BFS/DFS 预处理第一层祖先、深度、距离let mut q VecDeque::new();q.push_back(0);up[0][0] 0; // 根节点的父节点是自己let mut visited vec![false; n];visited[0] true;while let Some(u) q.pop_front() {for (v, w) in graph[u] {if !visited[v] {visited[v] true;up[v][0] u;depth[v] depth[u] 1;dist[v] dist[u] w as i64;q.push_back(v);}}}// 倍增表for j in 1..log_n {for v in 0..n {up[v][j] up[up[v][j - 1]][j - 1];}}// LCA 函数let lca |mut u: usize, mut v: usize| - usize {if depth[u] depth[v] {std::mem::swap(mut u, mut v);}// 将 v 提升到与 u 同一深度let diff depth[v] - depth[u];for j in 0..log_n {if (diff j) 1 1 {v up[v][j];}}if u v {return u;}// 从大到小跳for j in (0..log_n).rev() {if up[u][j] ! up[v][j] {u up[u][j];v up[v][j];}}up[u][0]};// 树上距离let distance |u: usize, v: usize| - i64 {let w lca(u, v);dist[u] dist[v] - 2 * dist[w]};// 回答每个查询queries.into_iter().map(|q| {let src1 q[0] as usize;let src2 q[1] as usize;let dest q[2] as usize;let d12 distance(src1, src2);let d1d distance(src1, dest);let d2d distance(src2, dest);((d12 d1d d2d) / 2) as i32}).collect()}}思路说明步骤 说明建图 无向带权树用邻接表存储BFS 预处理 以 0 为根计算每个节点的深度 depth[] 和到根的距离 dist[]同时记录每个节点的直接父节点 up[v][0]倍增表 up[v][j] 表示节点 v 的 2^j 级祖先O(n \log n) 预处理LCA 每次查询 O(\log n)先统一深度再同时向上跳树上距离 \text{dist}(u, v) \text{dist}[u] \text{dist}[v] - 2 \cdot \text{dist}[\text{lca}(u,v)]最终答案 对于每个查询(\text{dist}(src1, src2) \text{dist}(src1, dest) \text{dist}(src2, dest)) / 2复杂度- 时间O(n \log n q \log n)其中 q 为查询数- 空间O(n \log n) 注意dist 数组使用 i64因为 n \le 10^5边权 w_i \le 10^4最大距离约为 10^9虽然 i32 能放下但中间求和时三数相加可能溢出故用 i64 更安全。
这是 LeetCode 3553 的 Rust 实现。核心思路是答案 (dist(src1, src2) dist(src1, dest) dist(src2, dest)) / 2即三个点的最小连通子树的边权和等于两两距离之和除以 2。求树上距离需要用到 LCA 倍增。rustuse std::collections::VecDeque;struct Solution;impl Solution {pub fn minimum_weight(edges: VecVeci32, queries: VecVeci32) - Veci32 {let n edges.len() 1;if n 0 {return vec![];}// 建图let mut graph: VecVec(usize, i32) vec![vec![]; n];for e in edges {let u e[0] as usize;let v e[1] as usize;let w e[2];graph[u].push((v, w));graph[v].push((u, w));}// 倍增 LCA 预处理let log_n (n as f64).log2().ceil() as usize 1;let mut up vec![vec![0; log_n]; n]; // up[v][j] 2^j 级祖先let mut depth vec![0; n];let mut dist vec![0i64; n]; // 到根的距离用 i64 防溢出// BFS/DFS 预处理第一层祖先、深度、距离let mut q VecDeque::new();q.push_back(0);up[0][0] 0; // 根节点的父节点是自己let mut visited vec![false; n];visited[0] true;while let Some(u) q.pop_front() {for (v, w) in graph[u] {if !visited[v] {visited[v] true;up[v][0] u;depth[v] depth[u] 1;dist[v] dist[u] w as i64;q.push_back(v);}}}// 倍增表for j in 1..log_n {for v in 0..n {up[v][j] up[up[v][j - 1]][j - 1];}}// LCA 函数let lca |mut u: usize, mut v: usize| - usize {if depth[u] depth[v] {std::mem::swap(mut u, mut v);}// 将 v 提升到与 u 同一深度let diff depth[v] - depth[u];for j in 0..log_n {if (diff j) 1 1 {v up[v][j];}}if u v {return u;}// 从大到小跳for j in (0..log_n).rev() {if up[u][j] ! up[v][j] {u up[u][j];v up[v][j];}}up[u][0]};// 树上距离let distance |u: usize, v: usize| - i64 {let w lca(u, v);dist[u] dist[v] - 2 * dist[w]};// 回答每个查询queries.into_iter().map(|q| {let src1 q[0] as usize;let src2 q[1] as usize;let dest q[2] as usize;let d12 distance(src1, src2);let d1d distance(src1, dest);let d2d distance(src2, dest);((d12 d1d d2d) / 2) as i32}).collect()}}思路说明步骤 说明建图 无向带权树用邻接表存储BFS 预处理 以 0 为根计算每个节点的深度 depth[] 和到根的距离 dist[]同时记录每个节点的直接父节点 up[v][0]倍增表 up[v][j] 表示节点 v 的 2^j 级祖先O(n \log n) 预处理LCA 每次查询 O(\log n)先统一深度再同时向上跳树上距离 \text{dist}(u, v) \text{dist}[u] \text{dist}[v] - 2 \cdot \text{dist}[\text{lca}(u,v)]最终答案 对于每个查询(\text{dist}(src1, src2) \text{dist}(src1, dest) \text{dist}(src2, dest)) / 2复杂度- 时间O(n \log n q \log n)其中 q 为查询数- 空间O(n \log n) 注意dist 数组使用 i64因为 n \le 10^5边权 w_i \le 10^4最大距离约为 10^9虽然 i32 能放下但中间求和时三数相加可能溢出故用 i64 更安全。
