Struct LowestCommonAncestor

Source

pub struct LowestCommonAncestor {
    euler_tour: EulerTour<Visit>,
    trace: Vec<usize>,
    rmq: RangeMinimumQuery<u64>,
}

Fields§

§euler_tour: EulerTour<Visit>§trace: Vec<usize>§rmq: RangeMinimumQuery<u64>

Implementations§

Source §

impl LowestCommonAncestor

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_euler_tour(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, p: [usize]);
10    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
11    let tree = UndirectedSparseGraph::from_edges(n, edges);
12    let lca = tree.lca(0);
13    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
14        writeln!(writer, "{}", lca.lca(u, v)).ok();
15    }
16}

More examples

Hide additional examples

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

6pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, c: [SizedCollect<usize>]);
10    let edges = c
11        .take(n)
12        .enumerate()
13        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
14        .collect();
15    let tree = UndirectedSparseGraph::from_edges(n, edges);
16    let lca = tree.lca(0);
17    scan!(scanner, q, uv: [(usize, usize)]);
18    for (u, v) in uv.take(q) {
19        writeln!(writer, "{}", lca.lca(u, v)).ok();
20    }
21}

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

6pub fn jump_on_tree(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
10    let la = g.level_ancestor(0);
11    let lca = g.lca(0);
12    for _ in 0..q {
13        scan!(scanner, s, t, i);
14        let l = lca.lca(s, t);
15        let ds = la.depth(s) - la.depth(l);
16        let dt = la.depth(t) - la.depth(l);
17        let ans = if i <= ds {
18            la.la(s, i)
19        } else if i <= ds + dt {
20            la.la(t, ds + dt - i)
21        } else {
22            None
23        };
24        writeln!(writer, "{}", ans.unwrap_or(!0) as isize).ok();
25    }
26}
27
28#[verify::library_checker("jump_on_tree")]
29pub fn jump_on_tree_batch(reader: impl Read, mut writer: impl Write) {
30    let s = read_all_unchecked(reader);
31    let mut scanner = Scanner::new(&s);
32    scan!(scanner, n, q, (g, _): @TreeGraphScanner::<usize>::new(n), queries: [(usize, usize, usize)]);
33    let lca = g.lca(0);
34    let depth = g.tree_depth(0);
35    let results = g.level_ancestor_batch(
36        0,
37        queries.take(q).map(|(s, t, i)| {
38            let l = lca.lca(s, t);
39            let ds = (depth[s] - depth[l]) as usize;
40            let dt = (depth[t] - depth[l]) as usize;
41            if i <= ds {
42                (s, i)
43            } else if i <= ds + dt {
44                (t, ds + dt - i)
45            } else {
46                (0, n)
47            }
48        }),
49    );
50    iter_print!(writer, @lf @it results.iter().map(|&v| v.unwrap_or(!0) as isize));
51}