library_checker/tree/
vertex_add_subtree_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation, data_structure::SegmentTree, graph::UndirectedSparseGraph,
5};
6
7competitive::define_enum_scan! {
8    enum Query: usize {
9        0 => Add { u: usize, x: u64 }
10        1 => Sum { u: usize }
11    }
12}
13
14#[verify::library_checker("vertex_add_subtree_sum")]
15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

library_checker/tree/vertex_add_subtree_sum.rs

library_checker/tree/
vertex_add_subtree_sum.rs