aizu_online_judge/grl/
grl_5_d.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::AdditiveOperation, data_structure::BinaryIndexedTree, graph::UndirectedSparseGraph,
4    tools::SizedCollect,
5};
6
7competitive::define_enum_scan! {
8    enum Query: usize {
9        0 => Add { v: usize, w: i64 }
10        1 => Get { u: usize }
11    }
12}
13
14#[verify::aizu_online_judge("GRL_5_D")]
15pub fn grl_5_d(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 et = graph.path_euler_tour_builder(0).build();
24    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                et.update(v, w, -w, |k, x| bit.update(k, x));
32            }
33            Query::Get { u } => {
34                let ans = et.fold(u, |k| bit.accumulate(k));
35                pp!(ans);
36            }
37        }
38    }
39}
aizu_online_judge/grl/grl_5_d.rs

aizu_online_judge/grl/
grl_5_d.rs
