企业官网建设流程全解析

根据题目要求，对于树中任意两个节点 u 和 v，路径长度为 d（边数），使路径总代价为奇数的赋值方案数为 2^(d-1)。核心是快速求树上两点距离。

Rust 实现（使用二进制提升）

```rust
const MOD: i64 = 1_000_000_007;

impl Solution {
pub fn assign_edge_weights(edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
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 代替 DFS）

```rust
use std::collections::VecDeque;

const MOD: i64 = 1_000_000_007;

impl Solution {
pub fn assign_edge_weights(edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
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: &[Vec<usize>], log: usize) -> usize {
if depth[u] > depth[v] {
std::mem::swap(&mut u, &mut v);
}

// 提升 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 {
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 的简洁版本

```rust
const MOD: i64 = 1_000_000_007;

impl Solution {
pub fn assign_edge_weights(edges: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
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: &[Vec<usize>], depth: &mut [usize], up: &mut [Vec<usize>], 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;

// LCA
if 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()
}
}
```

完整测试代码

```rust
struct Solution;

fn main() {
// 测试用例 1
let 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]

// 测试用例 2
let 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 条边中选择奇数条赋值为 1
3. LCA 求距离：dist(u,v) = depth[u] + depth[v] - 2*depth[lca]
4. 快速幂预处理：避免每次查询重复计算 2 的幂