library_checker/tree/
dynamic_tree_vertex_add_path_sum.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::{AdditiveOperation, EmptyActLazy},
4    tree::{PathLinkCutTree, TopTree, TopTreeSpec},
5};
6
7struct SumTopTree;
8
9impl TopTreeSpec for SumTopTree {
10    type Info = i64;
11    type Point = i64;
12    type Path = (i64, i64);
13
14    fn vertex(info: &Self::Info) -> Self::Path {
15        (*info, *info)
16    }
17
18    fn add_vertex(point: &Self::Point, info: &Self::Info) -> Self::Path {
19        (*point + *info, *info)
20    }
21
22    fn add_edge(path: &Self::Path) -> Self::Point {
23        path.0
24    }
25
26    fn rake(left: &Self::Point, right: &Self::Point) -> Self::Point {
27        *left + *right
28    }
29
30    fn compress(left: &Self::Path, right: &Self::Path) -> Self::Path {
31        (left.0 + right.0, left.1 + right.1)
32    }
33
34    fn reverse(_path: &mut Self::Path) {}
35}
36
37competitive::define_enum_scan! {
38    enum Query: usize {
39        0 => Relink { u: usize, v: usize, w: usize, x: usize }
40        1 => Add { p: usize, x: i64 }
41        2 => Sum { u: usize, v: usize }
42    }
43}
44
45#[verify::library_checker("dynamic_tree_vertex_add_path_sum")]
46pub fn dynamic_tree_vertex_add_path_sum(reader: impl Read, writer: impl Write) {
47    prepare_io!(reader, writer);
48    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
49    let mut tree = PathLinkCutTree::<EmptyActLazy<AdditiveOperation<i64>>>::from_edges(a, &edges);
50    for _ in 0..q {
51        sc!(query: Query);
52        match query {
53            Query::Relink { u, v, w, x } => {
54                tree.cut(u, v);
55                tree.link(w, x);
56            }
57            Query::Add { p, x } => tree.modify(p, |value| *value + x),
58            Query::Sum { u, v } => {
59                pp!(tree.fold_path(u, v));
60            }
61        }
62    }
63}
64
65#[verify::library_checker("dynamic_tree_vertex_add_path_sum")]
66pub fn dynamic_tree_vertex_add_path_sum_top_tree(reader: impl Read, writer: impl Write) {
67    prepare_io!(reader, writer);
68    sc!(n, q, a: [i64; n], edges: [(usize, usize); n - 1]);
69    let mut tree = TopTree::<SumTopTree>::from_edges(a, &edges);
70    for _ in 0..q {
71        sc!(query: Query);
72        match query {
73            Query::Relink { u, v, w, x } => {
74                tree.cut(u, v);
75                tree.link(w, x);
76            }
77            Query::Add { p, x } => tree.modify(p, |value| *value + x),
78            Query::Sum { u, v } => {
79                pp!(tree.fold_path(u, v).1);
80            }
81        }
82    }
83}
library_checker/tree/dynamic_tree_vertex_add_path_sum.rs

library_checker/tree/
dynamic_tree_vertex_add_path_sum.rs
