Struct LevelAncestor 

pub struct LevelAncestor {
    parent: Vec<usize>,
    depth: Vec<usize>,
    start: Vec<usize>,
    index: Vec<usize>,
    ladder: Vec<usize>,
}

Fields

parent: Vec<usize>

depth: Vec<usize>

start: Vec<usize>

index: Vec<usize>

ladder: Vec<usize>

Implementations

impl LevelAncestor

pub fn la(&self, u: usize, k: usize) -> Option<usize>

Examples found in repository

crates/competitive/src/algorithm/doubling.rs (line 338)

    pub fn kth(&self, u: usize, k: usize) -> (usize, M::T) {
        let depth = self.depth_to_cycle[u];
        if k <= depth {
            let ancestor = self.la.la(u, k).unwrap();
            let acc = self.acc_to_ancestor(u, ancestor);
            return (ancestor, acc);
        }
        let entry = self.cycle_entry[u];
        let acc_tree = self.acc_to_ancestor(u, entry);
        let steps = k - depth;
        let pos = self.cycle_jump_from(entry, steps);
        let acc_cycle = self.cycle_acc_from(entry, steps);
        let acc = M::operate(&acc_tree, &acc_cycle);
        (pos, acc)
    }

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

pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let la = g.level_ancestor(0);
    let lca = g.lca(0);
    for _ in 0..q {
        sc!(s, t, i);
        let l = lca.lca(s, t);
        let dl = la.depth(l);
        let ds = la.depth(s) - dl;
        let dt = la.depth(t) - dl;
        let ans = if i <= ds {
            la.la(s, i)
        } else if i <= ds + dt {
            la.la(t, ds + dt - i)
        } else {
            None
        };
        pp!(ans.unwrap_or(!0) as isize);
    }
}

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

Examples found in repository

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

pub fn jump_on_tree_level_ancestor(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
    let la = g.level_ancestor(0);
    let lca = g.lca(0);
    for _ in 0..q {
        sc!(s, t, i);
        let l = lca.lca(s, t);
        let dl = la.depth(l);
        let ds = la.depth(s) - dl;
        let dt = la.depth(t) - dl;
        let ans = if i <= ds {
            la.la(s, i)
        } else if i <= ds + dt {
            la.la(t, ds + dt - i)
        } else {
            None
        };
        pp!(ans.unwrap_or(!0) as isize);
    }
}