Struct LevelAncestor

Source

pub struct LevelAncestor {
    vidx: Vec<usize>,
    inv_vidx: Vec<usize>,
    depth: Vec<usize>,
    start: Vec<usize>,
    bucket: Vec<usize>,
}

Fields§

§vidx: Vec<usize>§inv_vidx: Vec<usize>§depth: Vec<usize>§start: Vec<usize>§bucket: Vec<usize>

Implementations§

Source §

impl LevelAncestor

Source

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

Examples found in repository ?

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

335    pub fn kth(&self, u: usize, k: usize) -> (usize, M::T) {
336        let depth = self.depth_to_cycle[u];
337        if k <= depth {
338            let ancestor = self.la.la(u, k).unwrap();
339            let acc = self.acc_to_ancestor(u, ancestor);
340            return (ancestor, acc);
341        }
342        let entry = self.cycle_entry[u];
343        let acc_tree = self.acc_to_ancestor(u, entry);
344        let steps = k - depth;
345        let pos = self.cycle_jump_from(entry, steps);
346        let acc_cycle = self.cycle_acc_from(entry, steps);
347        let acc = M::operate(&acc_tree, &acc_cycle);
348        (pos, acc)
349    }

More examples

Hide additional examples

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

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}

Source

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

Examples found in repository ?

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

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}