aizu_online_judge/grl/
grl_5_c.rs1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{graph::UndirectedSparseGraph, tools::SizedCollect};
4
5#[verify::aizu_online_judge("GRL_5_C")]
6pub fn grl_5_c(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, c: [SizedCollect<usize>]);
10 let edges = c
11 .take(n)
12 .enumerate()
13 .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
14 .collect();
15 let tree = UndirectedSparseGraph::from_edges(n, edges);
16 let lca = tree.lca(0);
17 scan!(scanner, q, uv: [(usize, usize)]);
18 for (u, v) in uv.take(q) {
19 writeln!(writer, "{}", lca.lca(u, v)).ok();
20 }
21}