aizu_online_judge/grl/
grl_5_c.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    graph::UndirectedSparseGraph,
5    tools::SizedCollect,
6    tree::{EulerTourForRichVertex, LcaMonoidDefaultId},
7};
8
9#[verify::aizu_online_judge("GRL_5_C")]
10pub fn grl_5_c(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, c: [SizedCollect<usize>]);
14    let edges = c
15        .take(n)
16        .enumerate()
17        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
18        .collect();
19    let graph = UndirectedSparseGraph::from_edges(n, edges);
20    let et = EulerTourForRichVertex::new(0, &graph);
21    let lca = et.gen_lca::<LcaMonoidDefaultId>();
22    scan!(scanner, q, uv: [(usize, usize)]);
23    for (u, v) in uv.take(q) {
24        writeln!(writer, "{}", lca.lca(u, v)).ok();
25    }
26}
aizu_online_judge/grl/grl_5_c.rs

aizu_online_judge/grl/
grl_5_c.rs
