aizu_online_judge/grl/
grl_5_e.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::{AdditiveOperation, RangeSumRangeAdd},
5    data_structure::LazySegmentTree,
6    graph::UndirectedSparseGraph,
7    tools::SizedCollect,
8    tree::HeavyLightDecomposition,
9};
10
11competitive::define_enum_scan! {
12    enum Query: usize {
13        0 => Add { v: usize, w: u64 }
14        1 => Get { u: usize }
15    }
16}
17
18#[verify::aizu_online_judge("GRL_5_E")]
19pub fn grl_5_e(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, c: [SizedCollect<usize>]);
23    let edges = c
24        .take(n)
25        .enumerate()
26        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
27        .collect();
28    let mut graph = UndirectedSparseGraph::from_edges(n, edges);
29    let hld = HeavyLightDecomposition::new(0, &mut graph);
30    type M = (AdditiveOperation<u64>, AdditiveOperation<u64>);
31    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0u64, 1u64); n]);
32
33    scan!(scanner, q);
34    for _ in 0..q {
35        scan!(scanner, query: Query);
36        match query {
37            Query::Add { v, w } => {
38                hld.update(0, v, true, |l, r| seg.update(l..r, w));
39            }
40            Query::Get { u } => {
41                let ans = hld.query::<M, _>(0, u, true, |l, r| seg.fold(l..r)).0;
42                writeln!(writer, "{}", ans).ok();
43            }
44        }
45    }
46}
aizu_online_judge/grl/grl_5_e.rs

aizu_online_judge/grl/
grl_5_e.rs
