library_checker/tree/
vertex_get_range_contour_add_on_tree.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation, data_structure::BinaryIndexedTree, graph::TreeGraphScanner,
5    tree::ContourQueryRange,
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Add { v: usize, l: usize, r: usize, x: i64 }
11        1 => Get { v: usize }
12    }
13}
14
15#[verify::library_checker("vertex_get_range_contour_add_on_tree")]
16pub fn vertex_get_range_contour_add_on_tree(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, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(cq.len() + 1);
22
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |start, end| {
28                    bit.update(start, x);
29                    bit.update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |i| ans += bit.accumulate(i));
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

library_checker/tree/vertex_get_range_contour_add_on_tree.rs

library_checker/tree/
vertex_get_range_contour_add_on_tree.rs