library_checker/graph/
lca.rs

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

library_checker/graph/
lca.rs
