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
11#[verify::aizu_online_judge("GRL_5_E")]
12pub fn grl_5_e(reader: impl Read, mut writer: impl Write) {
13    let s = read_all_unchecked(reader);
14    let mut scanner = Scanner::new(&s);
15    scan!(scanner, n, c: [SizedCollect<usize>]);
16    let edges = c
17        .take(n)
18        .enumerate()
19        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
20        .collect();
21    let mut graph = UndirectedSparseGraph::from_edges(n, edges);
22    let hld = HeavyLightDecomposition::new(0, &mut graph);
23    type M = (AdditiveOperation<u64>, AdditiveOperation<u64>);
24    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_vec(vec![(0u64, 1u64); n]);
25
26    scan!(scanner, q);
27    for _ in 0..q {
28        match scanner.scan::<usize>() {
29            0 => {
30                scan!(scanner, v, w: u64);
31                hld.update(0, v, true, |l, r| seg.update(l..r, w));
32            }
33            1 => {
34                scan!(scanner, u);
35                let ans = hld.query::<M, _>(0, u, true, |l, r| seg.fold(l..r)).0;
36                writeln!(writer, "{}", ans).ok();
37            }
38            _ => panic!("unknown query"),
39        }
40    }
41}
aizu_online_judge/grl/grl_5_e.rs

aizu_online_judge/grl/
grl_5_e.rs
