library_checker/tree/
jump_on_tree.rs

1#[doc(no_inline)]
2pub use competitive::graph::{TreeGraphScanner, UndirectedSparseGraph};
3use competitive::prelude::*;
4
5#[verify::library_checker("jump_on_tree")]
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}
library_checker/tree/jump_on_tree.rs

library_checker/tree/
jump_on_tree.rs
