Struct EulerTourBuilder

Source

pub struct EulerTourBuilder<'a, K>where
    K: EulerTourKind,{
    tree: &'a UndirectedSparseGraph,
    root: usize,
    vidx: Vec<[usize; 2]>,
    eidx: Vec<[usize; 2]>,
    pos: usize,
    _marker: PhantomData<fn() -> K>,
}

Fields§

§tree: &'a UndirectedSparseGraph§root: usize§vidx: Vec<[usize; 2]>§eidx: Vec<[usize; 2]>§pos: usize§_marker: PhantomData<fn() -> K>

Implementations§

Source §

impl<'a, K> EulerTourBuilder<'a, K>
where K: EulerTourKind,

Source

pub fn new(tree: &'a UndirectedSparseGraph, root: usize) -> Self

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 174)

170    pub fn subtree_euler_tour_builder<'a>(
171        &'a self,
172        root: usize,
173    ) -> EulerTourBuilder<'a, marker::First> {
174        EulerTourBuilder::new(self, root)
175    }
176
177    pub fn path_euler_tour_builder<'a>(
178        &'a self,
179        root: usize,
180    ) -> EulerTourBuilder<'a, marker::FirstLast> {
181        EulerTourBuilder::new(self, root)
182    }
183
184    pub fn full_euler_tour_builder<'a>(
185        &'a self,
186        root: usize,
187    ) -> EulerTourBuilder<'a, marker::Visit> {
188        EulerTourBuilder::new(self, root)
189    }

Source

pub fn build_with_trace(self, trace: impl FnMut(usize)) -> EulerTour<K>

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 91)

90    pub fn build(self) -> EulerTour<K> {
91        self.build_with_trace(|_u| {})
92    }
93
94    fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize)) {
95        self.vidx[u][0] = self.pos;
96        trace(u);
97        self.pos += 1;
98        for a in self.tree.adjacencies(u) {
99            if a.to != parent {
100                self.eidx[a.id][0] = self.pos;
101                self.dfs(a.to, u, trace);
102                self.eidx[a.id][1] = self.pos;
103                if K::USE_VISIT {
104                    trace(u);
105                    self.pos += 1;
106                }
107            }
108        }
109        self.vidx[u][1] = self.pos;
110        if K::USE_LAST {
111            trace(u);
112            self.pos += 1;
113        }
114    }
115}
116
117impl EulerTourBuilder<'_, marker::First> {
118    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::First>, Vec<T>)
119    where
120        T: Clone,
121    {
122        assert_eq!(s.len(), self.tree.vertices_size());
123        let mut trace = Vec::with_capacity(marker::First::size(s.len()));
124        let tour = self.build_with_trace(|u| {
125            trace.push(s[u].clone());
126        });
127        (tour, trace)
128    }
129}
130
131impl EulerTourBuilder<'_, marker::FirstLast> {
132    pub fn build_with_rearrange<T>(
133        self,
134        s: &[T],
135        mut inverse: impl FnMut(T) -> T,
136    ) -> (EulerTour<marker::FirstLast>, Vec<T>)
137    where
138        T: Clone,
139    {
140        assert_eq!(s.len(), self.tree.vertices_size());
141        let mut visited = vec![false; s.len()];
142        let mut trace = Vec::with_capacity(marker::FirstLast::size(s.len()));
143        let tour = self.build_with_trace(|u| {
144            if !visited[u] {
145                trace.push(s[u].clone());
146                visited[u] = true;
147            } else {
148                trace.push(inverse(s[u].clone()));
149            }
150        });
151        (tour, trace)
152    }
153}
154
155impl EulerTourBuilder<'_, marker::Visit> {
156    pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<marker::Visit>, Vec<T>)
157    where
158        T: Clone,
159    {
160        assert_eq!(s.len(), self.tree.vertices_size());
161        let mut trace = Vec::with_capacity(marker::Visit::size(s.len()));
162        let tour = self.build_with_trace(|u| {
163            trace.push(s[u].clone());
164        });
165        (tour, trace)
166    }
167}
168
169impl UndirectedSparseGraph {
170    pub fn subtree_euler_tour_builder<'a>(
171        &'a self,
172        root: usize,
173    ) -> EulerTourBuilder<'a, marker::First> {
174        EulerTourBuilder::new(self, root)
175    }
176
177    pub fn path_euler_tour_builder<'a>(
178        &'a self,
179        root: usize,
180    ) -> EulerTourBuilder<'a, marker::FirstLast> {
181        EulerTourBuilder::new(self, root)
182    }
183
184    pub fn full_euler_tour_builder<'a>(
185        &'a self,
186        root: usize,
187    ) -> EulerTourBuilder<'a, marker::Visit> {
188        EulerTourBuilder::new(self, root)
189    }
190
191    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
192        let depth = self.tree_depth(root);
193        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
194        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
195        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
196            trace.push(u);
197            depth_trace.push(depth[u]);
198        });
199        let rmq = RangeMinimumQuery::new(depth_trace);
200        LowestCommonAncestor {
201            euler_tour,
202            trace,
203            rmq,
204        }
205    }

Source

pub fn build(self) -> EulerTour<K>

Examples found in repository ?

crates/aizu_online_judge/src/grl/grl_5_d.rs (line 26)

16pub fn grl_5_d(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, c: [SizedCollect<usize>]);
20    let edges = c
21        .take(n)
22        .enumerate()
23        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
24        .collect();
25    let graph = UndirectedSparseGraph::from_edges(n, edges);
26    let et = graph.path_euler_tour_builder(0).build();
27    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
28
29    scan!(scanner, q);
30    for _ in 0..q {
31        scan!(scanner, query: Query);
32        match query {
33            Query::Add { v, w } => {
34                et.update(v, w, -w, |k, x| bit.update(k, x));
35            }
36            Query::Get { u } => {
37                let ans = et.fold(u, |k| bit.accumulate(k));
38                writeln!(writer, "{}", ans).ok();
39            }
40        }
41    }
42}

Source

fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize))

Examples found in repository ?

crates/competitive/src/tree/euler_tour.rs (line 80)

79    pub fn build_with_trace(mut self, mut trace: impl FnMut(usize)) -> EulerTour<K> {
80        self.dfs(self.root, !0, &mut trace);
81        EulerTour {
82            root: self.root,
83            vidx: self.vidx,
84            eidx: self.eidx,
85            size: self.pos,
86            _marker: PhantomData,
87        }
88    }
89
90    pub fn build(self) -> EulerTour<K> {
91        self.build_with_trace(|_u| {})
92    }
93
94    fn dfs(&mut self, u: usize, parent: usize, trace: &mut impl FnMut(usize)) {
95        self.vidx[u][0] = self.pos;
96        trace(u);
97        self.pos += 1;
98        for a in self.tree.adjacencies(u) {
99            if a.to != parent {
100                self.eidx[a.id][0] = self.pos;
101                self.dfs(a.to, u, trace);
102                self.eidx[a.id][1] = self.pos;
103                if K::USE_VISIT {
104                    trace(u);
105                    self.pos += 1;
106                }
107            }
108        }
109        self.vidx[u][1] = self.pos;
110        if K::USE_LAST {
111            trace(u);
112            self.pos += 1;
113        }
114    }

Source §

impl EulerTourBuilder<'_, First>

Source

pub fn build_with_rearrange<T>(self, s: &[T]) -> (EulerTour<First>, Vec<T>)
where T: Clone,

Examples found in repository ?

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 21)

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}