Struct LowestCommonAncestor

pub struct LowestCommonAncestor<'a, D: LcaMonoidDispatch> { /* private fields */ }

Implementations

impl<D: LcaMonoidDispatch> LowestCommonAncestor<'_, D>

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

Examples found in repository

crates/library_checker/src/graph/lca.rs (line 18)

pub fn lca_euler_tour(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, p: [usize]);
    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let euler = EulerTourForRichVertex::new(0, &graph);
    let lca = euler.gen_lca::<LcaMonoidDefaultId>();
    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
        writeln!(writer, "{}", lca.lca(u, v)).ok();
    }
}

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

pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, c: [SizedCollect<usize>]);
    let edges = c
        .take(n)
        .enumerate()
        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
        .collect();
    let graph = UndirectedSparseGraph::from_edges(n, edges);
    let et = EulerTourForRichVertex::new(0, &graph);
    let lca = et.gen_lca::<LcaMonoidDefaultId>();
    scan!(scanner, q, uv: [(usize, usize)]);
    for (u, v) in uv.take(q) {
        writeln!(writer, "{}", lca.lca(u, v)).ok();
    }
}

Trait Implementations

impl<'a, D: Clone + LcaMonoidDispatch> Clone for LowestCommonAncestor<'a, D>

fn clone(&self) -> LowestCommonAncestor<'a, D>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a, D: Debug + LcaMonoidDispatch> Debug for LowestCommonAncestor<'a, D>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.