aizu_online_judge/grl/
grl_5_d.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation, data_structure::BinaryIndexedTree, graph::UndirectedSparseGraph,
5    tools::SizedCollect,
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Add { v: usize, w: i64 }
11        1 => Get { u: usize }
12    }
13}
14
15#[verify::aizu_online_judge("GRL_5_D")]
16pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, c: [SizedCollect<usize>]);
20    let edges = c
21        .take(n)
22        .enumerate()
23        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
24        .collect();
25    let graph = UndirectedSparseGraph::from_edges(n, edges);
26    let et = graph.path_euler_tour_builder(0).build();
27    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
28
29    scan!(scanner, q);
30    for _ in 0..q {
31        scan!(scanner, query: Query);
32        match query {
33            Query::Add { v, w } => {
34                et.update(v, w, -w, |k, x| bit.update(k, x));
35            }
36            Query::Get { u } => {
37                let ans = et.fold(u, |k| bit.accumulate(k));
38                writeln!(writer, "{}", ans).ok();
39            }
40        }
41    }
42}
aizu_online_judge/grl/grl_5_d.rs

aizu_online_judge/grl/
grl_5_d.rs
