competitive/tree/
mod.rs

1//! tree algorithms
2
3use crate::{
4    algebra::{LazyMapMonoid, Magma, Monoid, Unital},
5    algorithm::CartesianTree,
6    data_structure::{
7        Allocator, MemoryPool, RangeMinimumQuery, binary_search_tree, splay_operations,
8    },
9    graph::{Graph, UndirectedSparseGraph},
10    math::{ConvolveSteps, U64Convolve},
11    tools::{MarkedScan, RandomSpec, Scan, ScanSource, Xorshift},
12};
13
14#[codesnip::entry("centroid_decomposition")]
15pub use self::centroid_decomposition::ContourQueryRange;
16#[codesnip::entry("EulerTour")]
17pub use self::euler_tour::LowestCommonAncestor;
18#[codesnip::entry("tree_generator")]
19pub use self::generator::*;
20#[codesnip::entry("HeavyLightDecomposition")]
21pub use self::heavy_light_decomposition::{HeavyLightDecomposition, HeavyLightPathFold};
22#[codesnip::entry("LevelAncestor")]
23pub use self::level_ancestor::LevelAncestor;
24#[codesnip::entry("LinkCutTree")]
25pub use self::link_cut_tree::{
26    LinkCutTree, LinkCutTreePathFold, LinkCutTreePathUpdate, LinkCutTreeSpec,
27    LinkCutTreeSubtreeFold, LinkCutTreeSubtreeUpdate, PathLinkCutTree,
28};
29pub use self::rerooting::ReRooting;
30#[codesnip::entry("StaticTopTree")]
31pub use self::static_top_tree::{Cluster, MonoidCluster, StaticTopTree, StaticTopTreeDp};
32#[codesnip::entry("TopTree")]
33pub use self::top_tree::{NoTopTreeAction, TopTree, TopTreeAction, TopTreeSpec};
34pub use self::tree_center::*;
35pub use self::tree_hash::TreeHasher;
36#[codesnip::entry("XorLinkedRootedTree")]
37pub use self::xor_linked_tree::*;
38
39#[cfg_attr(
40    nightly,
41    codesnip::entry("centroid_decomposition", include("SparseGraph", "tree_order"))
42)]
43mod centroid_decomposition;
44mod depth;
45#[cfg_attr(
46    nightly,
47    codesnip::entry(
48        "distance_frequencies",
49        include("centroid_decomposition", "NumberTheoreticTransform")
50    )
51)]
52mod distance_frequencies;
53#[cfg_attr(
54    nightly,
55    codesnip::entry("EulerTour", include("RangeMinimumQuery", "SparseGraph", "tree_order"))
56)]
57mod euler_tour;
58#[cfg_attr(
59    nightly,
60    codesnip::entry("tree_generator", include("SparseGraph", "random_generator"))
61)]
62mod generator;
63#[cfg_attr(
64    nightly,
65    codesnip::entry(
66        "HeavyLightDecomposition",
67        include("algebra", "SparseGraph", "CartesianTree")
68    )
69)]
70mod heavy_light_decomposition;
71#[cfg_attr(
72    nightly,
73    codesnip::entry("LevelAncestor", include("SparseGraph", "tree_order"))
74)]
75mod level_ancestor;
76#[cfg_attr(
77    nightly,
78    codesnip::entry(
79        "LinkCutTree",
80        include("_splay_operations", "Allocator", "LazyMapMonoid")
81    )
82)]
83mod link_cut_tree;
84mod rerooting;
85#[cfg_attr(
86    nightly,
87    codesnip::entry("StaticTopTree", include("algebra", "SparseGraph"))
88)]
89mod static_top_tree;
90#[cfg_attr(
91    nightly,
92    codesnip::entry("TopTree", include("_splay_operations", "Allocator", "algebra"))
93)]
94mod top_tree;
95mod tree_center;
96#[cfg_attr(nightly, codesnip::entry("tree_centroid", include("SparseGraph")))]
97mod tree_centroid;
98mod tree_dp;
99mod tree_hash;
100mod tree_order;
101#[cfg_attr(nightly, codesnip::entry("XorLinkedRootedTree", include("scanner")))]
102mod xor_linked_tree;
competitive/tree/mod.rs

competitive/tree/
mod.rs
