1use crate::algebra::{Associative, Magma};
2use crate::data_structure::DisjointSparseTable;
3use crate::graph::UndirectedSparseGraph;
4
5#[codesnip::entry("EulerTourForEdge", include("SparseGraph"))]
6#[derive(Clone, Debug)]
7pub struct EulerTourForEdge<'a> {
8 graph: &'a UndirectedSparseGraph,
9 pub eidx: Vec<(usize, usize)>,
10 pub par: Vec<usize>,
11 epos: usize,
12}
13#[codesnip::entry("EulerTourForEdge")]
14impl<'a> EulerTourForEdge<'a> {
15 pub fn new(root: usize, graph: &'a UndirectedSparseGraph) -> Self {
16 let mut self_ = Self {
17 graph,
18 eidx: vec![(0, 0); graph.vertices_size() - 1],
19 par: vec![usize::MAX; graph.vertices_size()],
20 epos: 0,
21 };
22 self_.edge_tour(root, usize::MAX);
23 self_
24 }
25 pub fn length(&self) -> usize {
26 self.epos
27 }
28 fn edge_tour(&mut self, u: usize, p: usize) {
29 for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
30 self.par[a.to] = a.id;
31 self.eidx[a.id].0 = self.epos;
32 self.epos += 1;
33 self.edge_tour(a.to, u);
34 self.eidx[a.id].1 = self.epos;
35 self.epos += 1;
36 }
37 }
38}
39
40#[codesnip::entry("EulerTourForVertex", include("SparseGraph"))]
41#[derive(Clone, Debug)]
42pub struct EulerTourForVertex<'a> {
43 graph: &'a UndirectedSparseGraph,
44 pub vidx: Vec<(usize, usize)>,
45 vpos: usize,
46}
47#[codesnip::entry("EulerTourForVertex")]
48impl<'a> EulerTourForVertex<'a> {
49 pub fn new(graph: &'a UndirectedSparseGraph) -> Self {
50 Self {
51 graph,
52 vidx: vec![(0, 0); graph.vertices_size()],
53 vpos: 0,
54 }
55 }
56 pub fn length(&self) -> usize {
57 self.vpos
58 }
59 pub fn subtree_vertex_tour(&mut self, u: usize, p: usize) {
60 self.vidx[u].0 = self.vpos;
61 self.vpos += 1;
62 for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
63 self.subtree_vertex_tour(a.to, u);
64 }
65 self.vidx[u].1 = self.vpos;
66 }
67 pub fn path_vertex_tour(&mut self, u: usize, p: usize) {
68 self.vidx[u].0 = self.vpos;
69 self.vpos += 1;
70 for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
71 self.path_vertex_tour(a.to, u);
72 }
73 self.vidx[u].1 = self.vpos;
74 self.vpos += 1;
75 }
76 pub fn subtree_query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, mut f: F) -> T {
77 let (l, r) = self.vidx[u];
78 f(l, r)
79 }
80 pub fn subtree_update<T, F: FnMut(usize, T)>(&self, u: usize, x: T, mut f: F) {
81 let (l, _r) = self.vidx[u];
82 f(l, x);
83 }
84 pub fn path_query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, v: usize, mut f: F) -> T {
85 let (mut l, mut r) = (self.vidx[u].0, self.vidx[v].0);
86 if l > r {
87 std::mem::swap(&mut l, &mut r);
88 }
89 f(l, r + 1)
90 }
91 pub fn path_update<T, F: FnMut(usize, T)>(&self, u: usize, x: T, invx: T, mut f: F) {
92 let (l, r) = self.vidx[u];
93 f(l, x);
94 f(r, invx);
95 }
96}
97
98#[codesnip::entry("EulerTourForRichVertex", include("SparseGraph"))]
99#[derive(Clone, Debug)]
100pub struct EulerTourForRichVertex<'a> {
101 graph: &'a UndirectedSparseGraph,
102 pub root: usize,
103 pub vidx: Vec<(usize, usize)>,
104 vtrace: Vec<usize>,
105}
106#[codesnip::entry("EulerTourForRichVertex")]
107impl<'a> EulerTourForRichVertex<'a> {
108 pub fn new(root: usize, graph: &'a UndirectedSparseGraph) -> Self {
109 let mut self_ = Self {
110 graph,
111 root,
112 vidx: vec![(0, 0); graph.vertices_size()],
113 vtrace: vec![],
114 };
115 self_.vertex_tour(root, usize::MAX);
116 self_
117 }
118 pub fn length(&self) -> usize {
119 self.vtrace.len()
120 }
121 fn vertex_tour(&mut self, u: usize, p: usize) {
122 self.vidx[u].0 = self.vtrace.len();
123 self.vtrace.push(u);
124 for a in self.graph.adjacencies(u).filter(|a| a.to != p) {
125 self.vertex_tour(a.to, u);
126 self.vtrace.push(u);
127 }
128 self.vidx[u].1 = self.vtrace.len() - 1;
129 }
130 pub fn query<T, F: FnMut(usize, usize) -> T>(&self, u: usize, v: usize, mut f: F) -> T {
131 let (mut l, mut r) = (self.vidx[u].0, self.vidx[v].0);
132 if l > r {
133 std::mem::swap(&mut l, &mut r);
134 }
135 f(l, r + 1)
136 }
137}
138
139#[codesnip::entry("LowestCommonAncestor")]
140impl<'a> EulerTourForRichVertex<'a> {
141 pub fn gen_lca<D: LcaMonoidDispatch>(&'a self) -> LowestCommonAncestor<'a, D> {
142 D::set_depth(self.graph.tree_depth(self.root));
143 let dst = DisjointSparseTable::<LcaMonoid<D>>::new(self.vtrace.clone());
144 LowestCommonAncestor { euler: self, dst }
145 }
146}
147#[codesnip::entry(
148 "LowestCommonAncestor",
149 include(
150 "algebra",
151 "DisjointSparseTable",
152 "EulerTourForRichVertex",
153 "SparseGraph",
154 "tree_depth"
155 )
156)]
157#[derive(Clone, Debug)]
158pub struct LowestCommonAncestor<'a, D: LcaMonoidDispatch> {
159 euler: &'a EulerTourForRichVertex<'a>,
160 dst: DisjointSparseTable<LcaMonoid<D>>,
161}
162#[codesnip::entry("LowestCommonAncestor")]
163impl<D: LcaMonoidDispatch> LowestCommonAncestor<'_, D> {
164 pub fn lca(&self, u: usize, v: usize) -> usize {
165 self.euler.query(u, v, |l, r| self.dst.fold(l, r))
166 }
167}
168#[codesnip::entry("LowestCommonAncestor")]
169pub trait LcaMonoidDispatch {
170 fn vsize() -> usize;
171 fn depth(u: usize) -> u64;
172 fn set_depth(depth: Vec<u64>);
173}
174#[codesnip::entry("LowestCommonAncestor")]
175pub enum LcaMonoidDefaultId {}
176#[codesnip::entry("LowestCommonAncestor")]
177#[derive(Clone, Debug)]
178pub struct LcaMonoid<D: LcaMonoidDispatch = LcaMonoidDefaultId> {
179 _marker: std::marker::PhantomData<fn() -> D>,
180}
181#[codesnip::entry("LowestCommonAncestor")]
182pub mod impl_lcam {
183 use super::*;
184 thread_local! {
185 static DEPTH: std::cell::Cell<Vec<u64>> = const { std::cell::Cell::new(Vec::new()) };
186 }
187 impl LcaMonoidDispatch for LcaMonoidDefaultId {
188 fn vsize() -> usize {
189 DEPTH.with(|c| unsafe { (*c.as_ptr()).len() })
190 }
191 fn depth(u: usize) -> u64 {
192 DEPTH.with(|c| unsafe { (&*c.as_ptr())[u] })
193 }
194 fn set_depth(depth: Vec<u64>) {
195 DEPTH.with(|c| c.set(depth))
196 }
197 }
198 impl<D: LcaMonoidDispatch> Magma for LcaMonoid<D> {
199 type T = usize;
200 fn operate(&x: &Self::T, &y: &Self::T) -> Self::T {
201 if x >= D::vsize() {
202 y
203 } else if y >= D::vsize() || D::depth(x) < D::depth(y) {
204 x
205 } else {
206 y
207 }
208 }
209 }
210 impl<D: LcaMonoidDispatch> Associative for LcaMonoid<D> {}
211}