haar_lib/tree/
auxiliary_tree.rs

1//! Auxiliary Tree
2//!
3//! # References
4//! - <https://noshi91.github.io/algorithm-encyclopedia/auxiliary-tree>
5
6use crate::tree::*;
7
8/// Auxiliary Tree
9///
10/// 与えられた頂点集合とそのLCAを保って木を圧縮した木を生成する。
11pub struct AuxiliaryTree {
12    preorder: Vec<usize>,
13}
14
15impl AuxiliaryTree {
16    /// `AuxiliaryTree`を生成する。
17    pub fn new<E: TreeEdgeTrait>(tree: &Tree<E>, root: usize) -> Self {
18        let n = tree.len();
19        let mut this = Self {
20            preorder: vec![0; n],
21        };
22        this.dfs(tree, root, None, &mut 0);
23        this
24    }
25
26    fn dfs<E: TreeEdgeTrait>(
27        &mut self,
28        tree: &Tree<E>,
29        cur: usize,
30        par: Option<usize>,
31        i: &mut usize,
32    ) {
33        self.preorder[cur] = *i;
34        *i += 1;
35
36        for e in tree.nodes[cur].neighbors() {
37            if par.is_none_or(|p| p != e.to()) {
38                self.dfs(tree, e.to(), Some(cur), i);
39            }
40        }
41    }
42
43    /// 頂点集合`vs`からAuxiliaryTreeを構築する。
44    pub fn build<F>(&self, mut vs: Vec<usize>, lca: F) -> Vec<usize>
45    where
46        F: Fn(usize, usize) -> usize,
47    {
48        vs.sort_by(|&a, &b| self.preorder[a].cmp(&self.preorder[b]));
49
50        let n = vs.len();
51        for i in 0..n - 1 {
52            let x = lca(vs[i], vs[i + 1]);
53            vs.push(x);
54        }
55
56        vs.sort_by(|&a, &b| self.preorder[a].cmp(&self.preorder[b]));
57        vs.dedup();
58        vs
59    }
60}
haar_lib/tree/auxiliary_tree.rs

haar_lib/tree/
auxiliary_tree.rs
