aizu_online_judge/grl/
grl_5_e.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::RangeSumRangeAdd, data_structure::LazySegmentTree, graph::UndirectedSparseGraph,
4    tools::SizedCollect,
5};
6
7competitive::define_enum_scan! {
8    enum Query: usize {
9        0 => Add { v: usize, w: u64 }
10        1 => Get { u: usize }
11    }
12}
13
14#[verify::aizu_online_judge("GRL_5_E")]
15pub fn grl_5_e(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let hld = graph.hld(0);
24    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0u64, n));
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                hld.path_edges(0, v, |l, r| seg.update(l..r, w));
32            }
33            Query::Get { u } => {
34                let mut ans = 0;
35                hld.path_edges(0, u, |l, r| ans += seg.fold(l..r).0);
36                pp!(ans);
37            }
38        }
39    }
40}
aizu_online_judge/grl/grl_5_e.rs

aizu_online_judge/grl/
grl_5_e.rs
