深入理解树链剖分（Rust语言实现详解）

为什么选择 Rust 实现？

Rust 提供了内存安全、零成本抽象和高性能并发能力，非常适合实现如 Rust图论算法 这类对性能敏感的数据结构。同时，Rust 的类型系统和所有权模型能帮助我们在编译期避免许多常见错误。

算法步骤概览

1. 第一次 DFS：计算每个节点的子树大小、深度、父节点，并确定“重儿子”（子树最大的孩子）。
2. 第二次 DFS：按重儿子优先的顺序进行遍历，为每个节点分配在线段树中的位置（称为 DFS 序），并记录所在重链的顶端节点。
3. 构建线段树：基于 DFS 序建立支持区间查询/更新的数据结构。
4. 路径操作：利用重链性质，将任意路径拆解为若干链段，在线段树上执行操作。

Rust 实现细节

下面我们将逐步用 Rust 实现树链剖分。为了简化，我们假设树以邻接表形式给出，且节点编号从 0 开始。

1. 定义基础结构

struct Tree {    n: usize,    graph: Vec<Vec<usize>>,    parent: Vec<usize>,    depth: Vec<usize>,    size: Vec<usize>,    heavy: Vec<i32>, // -1 表示无重儿子    head: Vec<usize>,    pos: Vec<usize>,    curr_pos: usize,}

2. 第一次 DFS：计算子树大小与重儿子

impl Tree {    fn dfs_size(&mut self, u: usize, p: usize) -> usize {        self.parent[u] = p;        self.size[u] = 1;        let mut max_size = 0;        for &v in &self.graph[u] {            if v != p {                self.depth[v] = self.depth[u] + 1;                let child_size = self.dfs_size(v, u);                self.size[u] += child_size;                if child_size > max_size {                    max_size = child_size;                    self.heavy[u] = v as i32;                }            }        }        self.size[u]    }}

3. 第二次 DFS：分配 DFS 序与链顶

impl Tree {    fn decompose(&mut self, u: usize, h: usize) {        self.head[u] = h;        self.pos[u] = self.curr_pos;        self.curr_pos += 1;        if self.heavy[u] != -1 {            // 先遍历重儿子，保证重链连续            self.decompose(self.heavy[u] as usize, h);        }        for &v in &self.graph[u] {            if v != self.parent[u] && v != self.heavy[u] as usize {                // 轻儿子开启新链                self.decompose(v, v);            }        }    }}

4. 初始化树链剖分

impl Tree {    fn new(graph: Vec<Vec<usize>>) -> Self {        let n = graph.len();        let mut tree = Tree {            n,            graph,            parent: vec![0; n],            depth: vec![0; n],            size: vec![0; n],            heavy: vec![-1; n],            head: vec![0; n],            pos: vec![0; n],            curr_pos: 0,        };        tree.dfs_size(0, 0);        tree.decompose(0, 0);        tree    }}

应用场景与扩展

树链剖分常用于解决以下问题：

• 路径最大值/最小值/和查询
• 子树更新与查询
• 动态维护树上信息

结合线段树后，你可以轻松实现这些功能。这也是 Rust数据结构 在竞赛和工程中大放异彩的典型例子。

结语

通过本教程，你已经掌握了如何在 Rust 中实现树链剖分。虽然代码略长，但只要理解两次 DFS 的作用，就能灵活应用。希望这篇 Rust编程教程 能为你打开高级图论算法的大门！

© 2023 Rust 算法学习指南 | 树链剖分专题