Kimi LeetCode 3553. 包含要求路径的最小带权子图 II Rust实现-北京尧图网络

这是 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 更安全。

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

相关推荐

MSP430FR599x/FR596x FRAM与LEA技术解析：超低功耗嵌入式信号处理实战

QPSK/DQPSK 调制解调系统仿真：从星座图到相位模糊的实战解析

AI代理协作系统：模拟游戏工作室的LLM结构化应用实践

更多资讯

Claude Code で OpenCodeReview（OCR）を動かす：スラッシュコマンドによるエンドツーエンドのコードレビュー

Hive主键约束真相：DISABLE NOVALIDATE与RELY实战指南

gpt-image-2实战指南：从资源整合到参数调优与稳定出图

如何对本地 FASTQ 运行 nf-core/rnaseq 完成 RNA-seq 差异表达分析

LBMPC与MATLAB融合实践：工业控制中的智能优化

MindSpore视觉训练学习率调度实战：从原理到代码

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？