Struct LowestCommonAncestor

Source

pub struct LowestCommonAncestor {
    node_to_index: Vec<u32>,
    label_to_node: Vec<u32>,
    rmq: RangeMinimumQuery<u32>,
    depth: Vec<u32>,
}

Fields§

§node_to_index: Vec<u32>§label_to_node: Vec<u32>§rmq: RangeMinimumQuery<u32>§depth: Vec<u32>

Implementations§

Source §

impl LowestCommonAncestor

Source

pub fn from_parents(parents: &[usize]) -> Self

parents must contain one parent per vertex and use !0 for the root.

Examples found in repository ?

crates/library_checker/src/tree/lca.rs (line 11)

6pub fn lca(reader: impl Read, writer: impl Write) {
7    prepare_io!(reader, writer);
8    sc!(n, q, p: [usize; iter n - 1]);
9    let mut parents = vec![!0];
10    parents.extend(p);
11    let lca = LowestCommonAncestor::from_parents(&parents);
12    for _ in 0..q {
13        sc!(u, v);
14        pp!(lca.lca(u, v));
15    }
16}

Source

pub fn from_dfs_preorder(parents: &[usize], order: &[usize]) -> Self

order must be a DFS preorder containing every vertex in parents exactly once. parents uses !0 for the root.

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 193)

191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let (order, parents) = self.tree_order(root);
193        LowestCommonAncestor::from_dfs_preorder(&parents, &order)
194    }

More examples

Hide additional examples

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 21)

16pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, mut a: [i64; n],
19        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
20            .with_parent().with_dfs_preorder());
21    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
22    let mut values = vec![0; n + 1];
23    for (u, &x) in a.iter().enumerate() {
24        let range = tree.subtree_range(u);
25        values[range.start] += x;
26        values[range.end] -= x;
27    }
28    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
29    for _ in 0..q {
30        sc!(query: Query);
31        match query {
32            Query::Add { p, x } => {
33                a[p] += x;
34                let range = tree.subtree_range(p);
35                bit.update(range.start, x);
36                bit.update(range.end, -x);
37            }
38            Query::Sum { u, v } => {
39                let p = lca.lca(u, v);
40                pp!(
41                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
42                        - 2 * bit.accumulate(tree.dfs_index(p))
43                );
44            }
45        }
46    }
47}

Source

pub fn depth(&self, u: usize) -> usize

Examples found in repository ?

crates/library_checker/src/tree/jump_on_tree.rs (line 47)

39pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
40    prepare_io!(reader, writer);
41    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
42    let lca = g.lca(0);
43    let results = g.level_ancestor_batch(
44        0,
45        queries.map(|(s, t, i)| {
46            let l = lca.lca(s, t);
47            let dl = lca.depth(l);
48            let ds = lca.depth(s) - dl;
49            let dt = lca.depth(t) - dl;
50            if i <= ds {
51                (s, i)
52            } else if i <= ds + dt {
53                (t, ds + dt - i)
54            } else {
55                (0, n)
56            }
57        }),
58    );
59    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
60}

Source

pub fn lca(&self, u: usize, v: usize) -> usize

Examples found in repository ?

crates/library_checker/src/tree/lca.rs (line 14)

6pub fn lca(reader: impl Read, writer: impl Write) {
7    prepare_io!(reader, writer);
8    sc!(n, q, p: [usize; iter n - 1]);
9    let mut parents = vec![!0];
10    parents.extend(p);
11    let lca = LowestCommonAncestor::from_parents(&parents);
12    for _ in 0..q {
13        sc!(u, v);
14        pp!(lca.lca(u, v));
15    }
16}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_5_c.rs (line 16)

5pub fn grl_5_c(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, c: [SizedCollect<usize>; iter n]);
8    let edges = c
9        .enumerate()
10        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
11        .collect();
12    let tree = UndirectedSparseGraph::from_edges(n, edges);
13    let lca = tree.lca(0);
14    sc!(q, uv: [(usize, usize); iter q]);
15    for (u, v) in uv {
16        pp!(lca.lca(u, v));
17    }
18}

crates/library_checker/src/tree/jump_on_tree.rs (line 23)

16pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
19    let la = g.level_ancestor(0);
20    let lca = g.lca(0);
21    for _ in 0..q {
22        sc!(s, t, i);
23        let l = lca.lca(s, t);
24        let dl = la.depth(l);
25        let ds = la.depth(s) - dl;
26        let dt = la.depth(t) - dl;
27        let ans = if i <= ds {
28            la.la(s, i)
29        } else if i <= ds + dt {
30            la.la(t, ds + dt - i)
31        } else {
32            None
33        };
34        pp!(ans.unwrap_or(!0) as isize);
35    }
36}
37
38#[verify::library_checker("jump_on_tree")]
39pub fn jump_on_tree_level_ancestor_batch(reader: impl Read, writer: impl Write) {
40    prepare_io!(reader, writer);
41    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize); iter q]);
42    let lca = g.lca(0);
43    let results = g.level_ancestor_batch(
44        0,
45        queries.map(|(s, t, i)| {
46            let l = lca.lca(s, t);
47            let dl = lca.depth(l);
48            let ds = lca.depth(s) - dl;
49            let dt = lca.depth(t) - dl;
50            if i <= ds {
51                (s, i)
52            } else if i <= ds + dt {
53                (t, ds + dt - i)
54            } else {
55                (0, n)
56            }
57        }),
58    );
59    pp!(@lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
60}

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 39)

16pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, mut a: [i64; n],
19        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
20            .with_parent().with_dfs_preorder());
21    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
22    let mut values = vec![0; n + 1];
23    for (u, &x) in a.iter().enumerate() {
24        let range = tree.subtree_range(u);
25        values[range.start] += x;
26        values[range.end] -= x;
27    }
28    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
29    for _ in 0..q {
30        sc!(query: Query);
31        match query {
32            Query::Add { p, x } => {
33                a[p] += x;
34                let range = tree.subtree_range(p);
35                bit.update(range.start, x);
36                bit.update(range.end, -x);
37            }
38            Query::Sum { u, v } => {
39                let p = lca.lca(u, v);
40                pp!(
41                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
42                        - 2 * bit.accumulate(tree.dfs_index(p))
43                );
44            }
45        }
46    }
47}