以下是 LeetCode 3547. 图中边值的最大和 的 Rust 实现。解题思路由于每个节点最多与其他两个节点相连整个图由若干链和环组成。1. 连通分量分类用 DFS 找出所有连通分量。若分量内所有节点度数均为 2则为环否则为链孤立点不贡献边权忽略。2. 处理顺序先处理环每个节点有两条边大数在环中能产生更多乘积再处理链按长度降序长链优先拿大数。3. 填数策略将剩余的最大数放在连通分量中间次大数交替向两边扩展使得大数尽量相邻双端队列模拟。时间复杂度 O(n \log n)空间复杂度 O(n)。---Rust 代码rustuse std::collections::VecDeque;struct Solution;impl Solution {pub fn max_score(n: i32, edges: VecVeci32) - i64 {let n n as usize;let mut graph vec![vec![]; n];for edge in edges {let u edge[0] as usize;let v edge[1] as usize;graph[u].push(v);graph[v].push(u);}let mut seen vec![false; n];let mut cycle_sizes vec![];let mut path_sizes vec![];// 遍历每个连通分量for i in 0..n {if seen[i] {continue;}// DFS 收集连通分量let mut component vec![];let mut stack vec![i];seen[i] true;while let Some(u) stack.pop() {component.push(u);for v in graph[u] {if !seen[v] {seen[v] true;stack.push(v);}}}// 判断是否为环所有节点度数均为 2let is_cycle component.iter().all(|u| graph[u].len() 2);if is_cycle {cycle_sizes.push(component.len());} else if component.len() 1 {path_sizes.push(component.len());}// 孤立点size 1不贡献边权无需处理}let mut ans: i64 0;let mut remaining n as i64;// 先处理环从剩余的最大数中分配for size in cycle_sizes {let size size as i64;ans Self::calc_score(remaining - size 1, remaining, true);remaining - size;}// 链按长度从大到小排序优先处理长链path_sizes.sort_by(|a, b| b.cmp(a));for size in path_sizes {let size size as i64;ans Self::calc_score(remaining - size 1, remaining, false);remaining - size;}ans}/// 将 [left, right] 范围内的数填入一个连通分量计算最大边权和。////// 策略双端队列模拟中间放大数向两边递减的排列。/// 初始放入两个 right从 right-1 递减到 left每次取出队首与当前值相乘/// 再将当前值放入队尾。fn calc_score(left: i64, right: i64, is_cycle: bool) - i64 {let mut dq VecDeque::new();dq.push_back(right);dq.push_back(right);let mut score: i64 0;for val in (left..right).rev() {let window_val dq.pop_front().unwrap();score window_val * val;dq.push_back(val);}// 如果是环首尾两个节点也相邻额外加上首尾乘积if is_cycle {score dq.front().unwrap() * dq.back().unwrap();}score}}---关键说明要点 说明连通分量分类 所有节点度数均为 2 → 环否则为链含孤立点处理顺序 环优先于链因为环的每个节点都有两条边大数在环中能产生更多乘积链按长度降序长链优先拿大数calc_score 双端队列模拟最优排列。例如 [7..11] 填入 5 个节点的链排列为 8-10-11-9-7边权和最大环额外处理 环首尾相连所以 dq.front() * dq.back() 是最后一条边的贡献