library_checker/tree/
lca.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{graph::UndirectedSparseGraph, tree::HeavyLightDecomposition};
4
5#[verify::library_checker("lca")]
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}
17
18#[verify::library_checker("lca")]
19pub fn lca_hld(reader: impl Read, mut writer: impl Write) {
20    let s = read_all_unchecked(reader);
21    let mut scanner = Scanner::new(&s);
22    scan!(scanner, n, q, p: [usize]);
23    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
24    let mut graph = UndirectedSparseGraph::from_edges(n, edges);
25    let hld = HeavyLightDecomposition::new(0, &mut graph);
26    for (u, v) in scanner.iter::<(usize, usize)>().take(q) {
27        writeln!(writer, "{}", hld.lca(u, v)).ok();
28    }
29}
library_checker/tree/lca.rs

library_checker/tree/
lca.rs
