library_checker/tree/
dynamic_tree_vertex_set_path_composite.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::{Associative, EmptyAct, LazyMapMonoid, LinearOperation, Magma, Unital},
4    num::mint_basic::MInt998244353 as M,
5    tree::{PathLinkCutTree, TopTree, TopTreeSpec},
6};
7
8type Affine = (M, M);
9
10struct BidirectionalAffine;
11
12impl Magma for BidirectionalAffine {
13    type T = (Affine, Affine);
14
15    fn operate(left: &Self::T, right: &Self::T) -> Self::T {
16        (
17            LinearOperation::operate(&left.0, &right.0),
18            LinearOperation::operate(&right.1, &left.1),
19        )
20    }
21}
22
23impl Unital for BidirectionalAffine {
24    fn unit() -> Self::T {
25        let unit = LinearOperation::unit();
26        (unit, unit)
27    }
28}
29
30impl Associative for BidirectionalAffine {}
31
32struct PathComposite;
33
34impl LazyMapMonoid for PathComposite {
35    type Key = Affine;
36    type Agg = (Affine, Affine);
37    type Act = ();
38    type AggMonoid = BidirectionalAffine;
39    type ActMonoid = ();
40    type KeyAct = EmptyAct<Affine>;
41
42    fn single_agg(key: &Self::Key) -> Self::Agg {
43        (*key, *key)
44    }
45
46    fn toggle(value: &mut Self::Agg) {
47        std::mem::swap(&mut value.0, &mut value.1);
48    }
49
50    fn act_agg(value: &Self::Agg, _action: &Self::Act) -> Option<Self::Agg> {
51        Some(*value)
52    }
53}
54
55impl TopTreeSpec for PathComposite {
56    type Info = Affine;
57    type Point = ();
58    type Path = (Affine, Affine);
59
60    fn vertex(info: &Self::Info) -> Self::Path {
61        (*info, *info)
62    }
63
64    fn add_vertex(_point: &Self::Point, info: &Self::Info) -> Self::Path {
65        (*info, *info)
66    }
67
68    fn add_edge(_path: &Self::Path) -> Self::Point {}
69
70    fn rake(_left: &Self::Point, _right: &Self::Point) -> Self::Point {}
71
72    fn compress(left: &Self::Path, right: &Self::Path) -> Self::Path {
73        BidirectionalAffine::operate(left, right)
74    }
75
76    fn reverse(path: &mut Self::Path) {
77        std::mem::swap(&mut path.0, &mut path.1);
78    }
79}
80
81competitive::define_enum_scan! {
82    enum Query: usize {
83        0 => Relink { u: usize, v: usize, w: usize, x: usize }
84        1 => Set { p: usize, cd: Affine }
85        2 => Apply { u: usize, v: usize, x: M }
86    }
87}
88
89#[verify::library_checker("dynamic_tree_vertex_set_path_composite")]
90pub fn dynamic_tree_vertex_set_path_composite(reader: impl Read, writer: impl Write) {
91    prepare_io!(reader, writer);
92    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
93    let mut tree = PathLinkCutTree::<PathComposite>::from_edges(ab, &edges);
94    for _ in 0..q {
95        sc!(query: Query);
96        match query {
97            Query::Relink { u, v, w, x } => {
98                tree.cut(u, v);
99                tree.link(w, x);
100            }
101            Query::Set { p, cd } => tree.set(p, cd),
102            Query::Apply { u, v, x } => {
103                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
104            }
105        }
106    }
107}
108
109#[verify::library_checker("dynamic_tree_vertex_set_path_composite")]
110pub fn dynamic_tree_vertex_set_path_composite_top_tree(reader: impl Read, writer: impl Write) {
111    prepare_io!(reader, writer);
112    sc!(n, q, ab: [Affine; n], edges: [(usize, usize); n - 1]);
113    let mut tree = TopTree::<PathComposite>::from_edges(ab, &edges);
114    for _ in 0..q {
115        sc!(query: Query);
116        match query {
117            Query::Relink { u, v, w, x } => {
118                tree.cut(u, v);
119                tree.link(w, x);
120            }
121            Query::Set { p, cd } => tree.set(p, cd),
122            Query::Apply { u, v, x } => {
123                pp!(LinearOperation::apply(&tree.fold_path(u, v).0, &x));
124            }
125        }
126    }
127}
library_checker/tree/dynamic_tree_vertex_set_path_composite.rs

library_checker/tree/
dynamic_tree_vertex_set_path_composite.rs
