根据题目要求对于树中任意两个节点 u 和 v路径长度为 d边数使路径总代价为奇数的赋值方案数为 2^(d-1)。核心是快速求树上两点距离。Rust 实现使用二进制提升rustconst MOD: i64 1_000_000_007;impl Solution {pub fn assign_edge_weights(edges: VecVeci32, queries: VecVeci32) - Veci32 {let n edges.len() 1;// 1. 建图无向树let mut graph vec![Vec::new(); n];for e in edges {let u (e[0] - 1) as usize;let v (e[1] - 1) as usize;graph[u].push(v);graph[v].push(u);}// 2. 预处理深度和倍增表let log (n as f64).log2().ceil() as usize 1;let mut depth vec![0; n];let mut up vec![vec![0; log]; n];// DFS 迭代构建避免递归栈溢出let mut stack vec![(0, usize::MAX)];let mut parent vec![usize::MAX; n];let mut order Vec::new();while let Some((node, par)) stack.pop() {parent[node] par;order.push(node);for nei in graph[node] {if nei ! par {depth[nei] depth[node] 1;stack.push((nei, node));}}}// 初始化 up[0]for i in 0..n {up[i][0] if parent[i] usize::MAX { i } else { parent[i] };}// 构建倍增表for j in 1..log {for i in 0..n {up[i][j] up[up[i][j-1]][j-1];}}// 3. 预处理 2 的幂次let mut pow2 vec![1; n 1];for i in 1..n {pow2[i] (pow2[i-1] as i64 * 2 % MOD) as i32;}// 4. LCA 闭包let get_lca |mut u: usize, mut v: usize| - usize {if depth[u] depth[v] {std::mem::swap(mut u, mut v);}// 将 v 提升到与 u 同深度let mut diff depth[v] - depth[u];let mut j 0;while diff 0 {if diff 1 1 {v up[v][j];}diff 1;j 1;}if u v {return u;}// 同时提升for j in (0..log).rev() {if up[u][j] ! up[v][j] {u up[u][j];v up[v][j];}}up[u][0]};// 5. 处理查询let mut ans Vec::with_capacity(queries.len());for q in queries {let u (q[0] - 1) as usize;let v (q[1] - 1) as usize;let lca get_lca(u, v);let dist depth[u] depth[v] - 2 * depth[lca];let result if dist 0 { 0 } else { pow2[dist - 1] };ans.push(result);}ans}}优化版本使用 BFS 代替 DFSrustuse std::collections::VecDeque;const MOD: i64 1_000_000_007;impl Solution {pub fn assign_edge_weights(edges: VecVeci32, queries: VecVeci32) - Veci32 {let n edges.len() 1;// 1. 建图let mut graph vec![Vec::new(); n];for e in edges {let u (e[0] - 1) as usize;let v (e[1] - 1) as usize;graph[u].push(v);graph[v].push(u);}// 2. BFS 预处理let log (n as f64).log2().ceil() as usize 1;let mut depth vec![0; n];let mut up vec![vec![0; log]; n];let mut parent vec![usize::MAX; n];let mut queue VecDeque::new();queue.push_back(0);parent[0] 0;while let Some(node) queue.pop_front() {for nei in graph[node] {if parent[nei] usize::MAX {parent[nei] node;depth[nei] depth[node] 1;queue.push_back(nei);}}}// 初始化 up[0]for i in 0..n {up[i][0] parent[i];}// 构建倍增表for j in 1..log {for i in 0..n {up[i][j] up[up[i][j-1]][j-1];}}// 3. 预处理 2 的幂let mut pow2 vec![1; n 1];for i in 1..n {pow2[i] ((pow2[i-1] as i64 * 2) % MOD) as i32;}// 4. LCA 函数fn get_lca(mut u: usize, mut v: usize, depth: [usize], up: [Vecusize], log: usize) - usize {if depth[u] depth[v] {std::mem::swap(mut u, mut v);}// 提升 vlet mut diff depth[v] - depth[u];let mut j 0;while diff 0 {if diff 1 1 {v up[v][j];}diff 1;j 1;}if u v {return u;}for j in (0..log).rev() {if up[u][j] ! up[v][j] {u up[u][j];v up[v][j];}}up[u][0]}// 5. 处理查询let mut ans Vec::with_capacity(queries.len());for q in queries {let u (q[0] - 1) as usize;let v (q[1] - 1) as usize;let lca get_lca(u, v, depth, up, log);let dist depth[u] depth[v] - 2 * depth[lca];ans.push(if dist 0 { 0 } else { pow2[dist - 1] });}ans}}使用递归 DFS 的简洁版本rustconst MOD: i64 1_000_000_007;impl Solution {pub fn assign_edge_weights(edges: VecVeci32, queries: VecVeci32) - Veci32 {let n edges.len() 1;let mut graph vec![Vec::new(); n];for e in edges {let u (e[0] - 1) as usize;let v (e[1] - 1) as usize;graph[u].push(v);graph[v].push(u);}let log (n as f64).log2().ceil() as usize 1;let mut depth vec![0; n];let mut up vec![vec![0; log]; n];// 递归 DFS注意n 很大时可能栈溢出fn dfs(node: usize, parent: usize, graph: [Vecusize], depth: mut [usize], up: mut [Vecusize], log: usize) {up[node][0] parent;for j in 1..log {up[node][j] up[up[node][j-1]][j-1];}for nei in graph[node] {if nei ! parent {depth[nei] depth[node] 1;dfs(nei, node, graph, depth, up, log);}}}dfs(0, 0, graph, mut depth, mut up, log);let mut pow2 vec![1; n 1];for i in 1..n {pow2[i] ((pow2[i-1] as i64 * 2) % MOD) as i32;}queries.iter().map(|q| {let mut u (q[0] - 1) as usize;let mut v (q[1] - 1) as usize;// LCAif depth[u] depth[v] {std::mem::swap(mut u, mut v);}let mut diff depth[v] - depth[u];let mut j 0;while diff 0 {if diff 1 1 {v up[v][j];}diff 1;j 1;}if u ! v {for j in (0..log).rev() {if up[u][j] ! up[v][j] {u up[u][j];v up[v][j];}}u up[u][0];}let dist depth[q[0] as usize - 1] depth[q[1] as usize - 1] - 2 * depth[u];if dist 0 { 0 } else { pow2[dist - 1] }}).collect()}}完整测试代码ruststruct Solution;fn main() {// 测试用例 1let edges vec![vec![0, 1],vec![1, 2],vec![1, 3],vec![1, 4],vec![2, 5],];let queries vec![vec![2, 3],vec![0, 2],];let result Solution::assign_edge_weights(edges, queries);println!({:?}, result); // 输出: [8, 4]// 测试用例 2let edges vec![vec![1, 0],vec![0, 2],];let queries vec![vec![0, 1],];let result Solution::assign_edge_weights(edges, queries);println!({:?}, result); // 输出: [1]}复杂度分析操作 时间复杂度 空间复杂度预处理 O(n log n) O(n log n)单次查询 O(log n) O(1)总体 O((n q) log n) O(n log n)其中 n 为节点数q 为查询数。核心原理1. 路径长度为 d树上两点间的边数2. 方案数 2^(d-1)从 d 条边中选择奇数条赋值为 13. LCA 求距离dist(u,v) depth[u] depth[v] - 2*depth[lca]4. 快速幂预处理避免每次查询重复计算 2 的幂