Rust树上倍增算法详解（LCA算法Rust实现与树结构编程入门）

为什么选择Rust实现？

Rust以其内存安全、零成本抽象和高性能著称，非常适合实现底层算法。通过本教程，你不仅能掌握树结构算法教程的核心思想，还能提升Rust编程入门实践能力。

算法步骤详解

1. 建树：使用邻接表存储无向树。
2. DFS预处理：计算每个节点的深度和直接父节点（即 $2^0$ 祖先）。
3. 倍增表构建：动态规划填充 up[node][k] 表，其中 up[node][k] 表示 node 向上跳 $2^k$ 步的祖先。
4. LCA查询：先将两节点调整至同一深度，再同步向上跳，直到父节点相同。

完整Rust代码实现

以下是一个完整的、可运行的Rust程序，实现了树上倍增求LCA：

use std::io;use std::collections::VecDeque;struct Tree {    n: usize,    graph: Vec<Vec<usize>>,    depth: Vec<i32>,    up: Vec<Vec<usize>>,    LOG: usize,}impl Tree {    fn new(n: usize) -> Self {        let log = (n as f64).log2().ceil() as usize + 1;        Tree {            n,            graph: vec![vec![]; n],            depth: vec![0; n],            up: vec![vec![0; log]; n],            LOG: log,        }    }    fn add_edge(&mut self, u: usize, v: usize) {        self.graph[u].push(v);        self.graph[v].push(u);    }    fn dfs(&mut self, u: usize, parent: usize) {        for &v in &self.graph[u] {            if v != parent {                self.depth[v] = self.depth[u] + 1;                self.up[v][0] = u;                self.dfs(v, u);            }        }    }    fn preprocess(&mut self) {        self.dfs(0, 0); // 假设根节点为0        for k in 1..self.LOG {            for v in 0..self.n {                let mid = self.up[v][k - 1];                self.up[v][k] = self.up[mid][k - 1];            }        }    }    fn lca(&self, mut u: usize, mut v: usize) -> usize {        if self.depth[u] < self.depth[v] {            std::mem::swap(&mut u, &mut v);        }        // 将u提升到与v同一深度        let mut diff = self.depth[u] - self.depth[v];        let mut k = 0;        while diff > 0 {            if diff & 1 == 1 {                u = self.up[u][k];            }            diff >>= 1;            k += 1;        }        if u == v {            return u;        }        // 同步向上跳        for k in (0..self.LOG).rev() {            if self.up[u][k] != self.up[v][k] {                u = self.up[u][k];                v = self.up[v][k];            }        }        self.up[u][0]    }}fn main() {    let mut input = String::new();    io::stdin().read_line(&mut input).unwrap();    let n: usize = input.trim().parse().unwrap();    let mut tree = Tree::new(n);    for _ in 0..n - 1 {        input.clear();        io::stdin().read_line(&mut input).unwrap();        let edges: Vec<usize> = input            .trim()            .split_whitespace()            .map(|x| x.parse().unwrap())            .collect();        tree.add_edge(edges[0], edges[1]);    }    tree.preprocess();    // 示例查询    println!("请输入两个节点查询LCA:");    input.clear();    io::stdin().read_line(&mut input).unwrap();    let query: Vec<usize> = input        .trim()        .split_whitespace()        .map(|x| x.parse().unwrap())        .collect();    let ans = tree.lca(query[0], query[1]);    println!("LCA of {} and {} is {}", query[0], query[1], ans);}

代码说明

• Tree::new 初始化树结构，LOG 表示最大跳跃指数（通常取 log₂(n)+1）。
• dfs 进行深度优先搜索，记录深度和直接父节点。
• preprocess 构建倍增表 up[v][k]。
• lca 函数先对齐深度，再同步向上跳，最终返回最近公共祖先。

总结

通过本教程，我们深入学习了Rust树上倍增算法的原理与实现，并成功用Rust编写了高效的LCA求解器。这不仅是一次树结构算法教程的实践，更是Rust编程入门的重要一步。掌握此类算法，将为你在算法竞赛或系统开发中打下坚实基础。

现在，你可以尝试修改代码，支持多组查询、动态加边，甚至扩展到求树上两点距离等问题！