library_checker/tree/
vertex_add_path_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation, data_structure::BinaryIndexedTree, graph::TreeGraphScanner,
5    tree::HeavyLightDecomposition,
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Add { p: usize, x: i64 }
11        1 => Sum { u: usize, v: usize }
12    }
13}
14
15#[verify::library_checker("vertex_add_path_sum")]
16pub fn vertex_add_path_sum(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, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let hld = HeavyLightDecomposition::new(0, &mut graph);
21    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
22    for (i, a) in a.iter().cloned().enumerate() {
23        bit.update(hld.vidx[i], a);
24    }
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::Add { p, x } => {
29                bit.update(hld.vidx[p], x);
30            }
31            Query::Sum { u, v } => {
32                writeln!(
33                    writer,
34                    "{}",
35                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
36                )
37                .ok();
38            }
39        }
40    }
41}
library_checker/tree/vertex_add_path_sum.rs

library_checker/tree/
vertex_add_path_sum.rs
