library_checker/tree/
lca.rs

1use competitive::graph::UndirectedSparseGraph;
2use competitive::prelude::*;
3use competitive::tree::LowestCommonAncestor;
4
5#[verify::library_checker("lca")]
6pub fn lca(reader: impl Read, writer: impl Write) {
7    prepare_io!(reader, writer);
8    sc!(n, q, p: [usize; iter n - 1]);
9    let mut parents = vec![!0];
10    parents.extend(p);
11    let lca = LowestCommonAncestor::from_parents(&parents);
12    for _ in 0..q {
13        sc!(u, v);
14        pp!(lca.lca(u, v));
15    }
16}
17
18#[verify::library_checker("lca")]
19pub fn lca_hld(reader: impl Read, writer: impl Write) {
20    prepare_io!(reader, writer);
21    sc!(n, q, p: [usize; iter n - 1]);
22    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
23    let graph = UndirectedSparseGraph::from_edges(n, edges);
24    let hld = graph.hld(0);
25    for _ in 0..q {
26        sc!(u, v);
27        pp!(hld.lca(u, v));
28    }
29}
library_checker/tree/lca.rs

library_checker/tree/
lca.rs
