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, tree::EulerTourForEdge,
6};
7
8#[verify::aizu_online_judge("GRL_5_D")]
9pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, c: [SizedCollect<usize>]);
13    let edges = c
14        .take(n)
15        .enumerate()
16        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
17        .collect();
18    let graph = UndirectedSparseGraph::from_edges(n, edges);
19    let et = EulerTourForEdge::new(0, &graph);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.length());
21
22    scan!(scanner, q);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, v, w: i64);
27                let (l, r) = et.eidx[et.par[v]];
28                bit.update(l, w);
29                bit.update(r, -w);
30            }
31            1 => {
32                scan!(scanner, u);
33                let ans = if u > 0 {
34                    bit.accumulate(et.eidx[et.par[u]].0)
35                } else {
36                    0
37                };
38                writeln!(writer, "{}", ans).ok();
39            }
40            _ => panic!("unknown query"),
41        }
42    }
43}
aizu_online_judge/grl/grl_5_d.rs

aizu_online_judge/grl/
grl_5_d.rs
