Skip to main content

HeavyLightDecomposition

competitive::tree::heavy_light_decomposition

Struct HeavyLightDecomposition 

Source 
pub struct HeavyLightDecomposition {
    nodes: Vec<HeavyLightNode>,
    order: Vec<usize>,
}

Fields§

§nodes: Vec<HeavyLightNode>§order: Vec<usize>

Implementations§

Source§

impl HeavyLightDecomposition

Source

pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 20)
19    pub fn hld(&self, root: usize) -> HeavyLightDecomposition {
20        HeavyLightDecomposition::new(root, self)
21    }
Source

pub fn len(&self) -> usize

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 101)
98    pub fn parent(&self, v: usize) -> Option<usize> {
99        let index = self.nodes[v].index as usize;
100        if index == self.nodes[v].head as usize {
101            ((self.nodes[v].parent as usize) < self.len()).then_some(self.nodes[v].parent as usize)
102        } else {
103            Some(self.order[index - 1])
104        }
105    }
106
107    #[inline]
108    pub fn index(&self, v: usize) -> usize {
109        self.nodes[v].index as usize
110    }
111
112    #[inline]
113    pub fn vertex(&self, index: usize) -> usize {
114        self.order[index]
115    }
116
117    #[inline]
118    pub fn subtree_size(&self, v: usize) -> usize {
119        self.nodes[v].size as usize
120    }
121
122    #[inline]
123    pub fn subtree_range(&self, v: usize) -> Range<usize> {
124        self.nodes[v].index as usize..self.nodes[v].index as usize + self.nodes[v].size as usize
125    }
126
127    #[inline]
128    pub fn is_ancestor(&self, ancestor: usize, v: usize) -> bool {
129        self.subtree_range(ancestor)
130            .contains(&(self.nodes[v].index as usize))
131    }
132
133    #[inline]
134    pub fn kth_ancestor(&self, mut v: usize, mut k: usize) -> Option<usize> {
135        loop {
136            let head = self.nodes[v].head as usize;
137            let chain_len = self.nodes[v].index as usize - head;
138            if k <= chain_len {
139                return Some(self.order[self.nodes[v].index as usize - k]);
140            }
141            k -= chain_len + 1;
142            v = self.nodes[v].parent as usize;
143            if v == self.len() {
144                return None;
145            }
146        }
147    }
148
149    #[inline]
150    pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
151        while self.nodes[u].head != self.nodes[v].head {
152            if self.nodes[u].index > self.nodes[v].index {
153                u = self.nodes[u].parent as usize;
154            } else {
155                v = self.nodes[v].parent as usize;
156            }
157        }
158        if self.nodes[u].index < self.nodes[v].index {
159            u
160        } else {
161            v
162        }
163    }
164
165    #[inline]
166    pub fn distance(&self, u: usize, v: usize) -> usize {
167        let (up, down) = self.path_lengths(u, v);
168        up + down
169    }
170
171    #[inline]
172    pub fn jump(&self, mut u: usize, mut v: usize, mut k: usize) -> Option<usize> {
173        let target = v;
174        let mut down = 0;
175        while self.nodes[u].head != self.nodes[v].head {
176            if self.nodes[u].index > self.nodes[v].index {
177                let up = self.nodes[u].index as usize - self.nodes[u].head as usize + 1;
178                if k < up {
179                    return Some(self.order[self.nodes[u].index as usize - k]);
180                }
181                k -= up;
182                u = self.nodes[u].parent as usize;
183            } else {
184                down += self.nodes[v].index as usize - self.nodes[v].head as usize + 1;
185                v = self.nodes[v].parent as usize;
186            }
187        }
188        if self.nodes[u].index >= self.nodes[v].index {
189            let up = self.nodes[u].index as usize - self.nodes[v].index as usize;
190            if k <= up {
191                return Some(self.order[self.nodes[u].index as usize - k]);
192            }
193            k -= up;
194        } else {
195            down += self.nodes[v].index as usize - self.nodes[u].index as usize;
196        }
197        down.checked_sub(k)
198            .and_then(|k| self.kth_ancestor(target, k))
199    }
200
201    #[inline]
202    fn path_lengths(&self, mut u: usize, mut v: usize) -> (usize, usize) {
203        let (mut up, mut down) = (0, 0);
204        while self.nodes[u].head != self.nodes[v].head {
205            if self.nodes[u].index > self.nodes[v].index {
206                up += self.nodes[u].index as usize - self.nodes[u].head as usize + 1;
207                u = self.nodes[u].parent as usize;
208            } else {
209                down += self.nodes[v].index as usize - self.nodes[v].head as usize + 1;
210                v = self.nodes[v].parent as usize;
211            }
212        }
213        if self.nodes[u].index > self.nodes[v].index {
214            up += self.nodes[u].index as usize - self.nodes[v].index as usize;
215        } else {
216            down += self.nodes[v].index as usize - self.nodes[u].index as usize;
217        }
218        (up, down)
219    }
220
221    /// Calls `f` once for each nonempty DFS-index range on the vertex path.
222    /// The callback order is unspecified.
223    #[inline]
224    pub fn path_vertices<F: FnMut(usize, usize)>(&self, u: usize, v: usize, f: F) {
225        self.path(u, v, false, f);
226    }
227
228    /// Calls `f` once for each nonempty DFS-index range on the edge path.
229    /// Each index represents the deeper endpoint of an edge. The callback order is unspecified.
230    #[inline]
231    pub fn path_edges<F: FnMut(usize, usize)>(&self, u: usize, v: usize, f: F) {
232        self.path(u, v, true, f);
233    }
234
235    #[inline]
236    fn path<F: FnMut(usize, usize)>(&self, mut u: usize, mut v: usize, is_edge: bool, mut f: F) {
237        loop {
238            if self.nodes[u].index > self.nodes[v].index {
239                std::mem::swap(&mut u, &mut v);
240            }
241            if self.nodes[u].head == self.nodes[v].head {
242                break;
243            }
244            f(
245                self.nodes[v].head as usize,
246                self.nodes[v].index as usize + 1,
247            );
248            v = self.nodes[v].parent as usize;
249        }
250        let l = self.nodes[u].index as usize + usize::from(is_edge);
251        let r = self.nodes[v].index as usize + 1;
252        if l < r {
253            f(l, r);
254        }
255    }
256
257    /// Folds a vertex path in `u`-to-`v` order.
258    /// `forward` folds a DFS-index range from left to right, and `reverse` folds it from right to
259    /// left.
260    #[inline]
261    pub fn fold_vertices<
262        M: Monoid,
263        F1: FnMut(usize, usize) -> M::T,
264        F2: FnMut(usize, usize) -> M::T,
265    >(
266        &self,
267        u: usize,
268        v: usize,
269        forward: F1,
270        reverse: F2,
271    ) -> M::T {
272        self.fold::<M, _, _>(u, v, false, forward, reverse)
273    }
274
275    /// Folds an edge path in `u`-to-`v` order.
276    /// Each index represents the deeper endpoint of an edge. `forward` folds a DFS-index range
277    /// from left to right, and `reverse` folds it from right to left.
278    #[inline]
279    pub fn fold_edges<
280        M: Monoid,
281        F1: FnMut(usize, usize) -> M::T,
282        F2: FnMut(usize, usize) -> M::T,
283    >(
284        &self,
285        u: usize,
286        v: usize,
287        forward: F1,
288        reverse: F2,
289    ) -> M::T {
290        self.fold::<M, _, _>(u, v, true, forward, reverse)
291    }
292
293    #[inline]
294    fn fold<M: Monoid, F1: FnMut(usize, usize) -> M::T, F2: FnMut(usize, usize) -> M::T>(
295        &self,
296        mut u: usize,
297        mut v: usize,
298        is_edge: bool,
299        mut forward: F1,
300        mut reverse: F2,
301    ) -> M::T {
302        let (mut left, mut right) = (M::unit(), M::unit());
303        while self.nodes[u].head != self.nodes[v].head {
304            if self.nodes[u].index > self.nodes[v].index {
305                left = M::operate(
306                    &left,
307                    &reverse(
308                        self.nodes[u].head as usize,
309                        self.nodes[u].index as usize + 1,
310                    ),
311                );
312                u = self.nodes[u].parent as usize;
313            } else {
314                right = M::operate(
315                    &forward(
316                        self.nodes[v].head as usize,
317                        self.nodes[v].index as usize + 1,
318                    ),
319                    &right,
320                );
321                v = self.nodes[v].parent as usize;
322            }
323        }
324        let middle = if self.nodes[u].index > self.nodes[v].index {
325            reverse(
326                self.nodes[v].index as usize + usize::from(is_edge),
327                self.nodes[u].index as usize + 1,
328            )
329        } else {
330            forward(
331                self.nodes[u].index as usize + usize::from(is_edge),
332                self.nodes[v].index as usize + 1,
333            )
334        };
335        M::operate(&M::operate(&left, &middle), &right)
336    }
337}
338
339pub struct HeavyLightPathFold<'a, M: Monoid> {
340    tree: &'a HeavyLightDecomposition,
341    nodes: Vec<PathFoldNode<M::T>>,
342}
343
344struct PathFoldNode<T> {
345    parent: u32,
346    children: [u32; 2],
347    priority: u32,
348    value: T,
349    aggregate: [T; 2],
350    prefix: [T; 2],
351}
352
353impl HeavyLightDecomposition {
354    /// `values` is indexed by vertex, not by DFS index.
355    pub fn build_fold<M: Monoid>(&self, values: &[M::T]) -> HeavyLightPathFold<'_, M> {
356        assert_eq!(values.len(), self.len());
357        let mut fold = HeavyLightPathFold {
358            tree: self,
359            nodes: self
360                .order
361                .iter()
362                .map(|&v| PathFoldNode {
363                    parent: u32::MAX,
364                    children: [u32::MAX; 2],
365                    priority: 0,
366                    value: values[v].clone(),
367                    aggregate: [values[v].clone(), values[v].clone()],
368                    prefix: [values[v].clone(), values[v].clone()],
369                })
370                .collect(),
371        };
372        let mut start = 0;
373        let mut priorities = Vec::new();
374        let mut stack = Vec::new();
375        while start < self.len() {
376            let mut end = start + 1;
377            while end < self.len() && self.nodes[self.order[end]].head as usize == start {
378                end += 1;
379            }
380            priorities.clear();
381            let mut sum = 0usize;
382            for i in start..end {
383                let weight = self.subtree_size(self.order[i])
384                    - if i + 1 < end {
385                        self.subtree_size(self.order[i + 1])
386                    } else {
387                        0
388                    };
389                let priority = (sum ^ (sum + weight)).ilog2();
390                sum += weight;
391                fold.nodes[i].priority = priority;
392                priorities.push(std::cmp::Reverse(priority));
393            }
394            let cartesian = CartesianTree::new(&priorities);
395            for i in start..end {
396                let parent = cartesian.parents[i - start];
397                fold.nodes[i].parent = if parent == usize::MAX {
398                    u32::MAX
399                } else {
400                    (parent + start) as u32
401                };
402                fold.nodes[i].children = cartesian.children[i - start].map(|v| {
403                    if v == usize::MAX {
404                        u32::MAX
405                    } else {
406                        (v + start) as u32
407                    }
408                });
409            }
410            stack.clear();
411            stack.push(cartesian.root + start);
412            let mut i = 0;
413            while i < stack.len() {
414                stack.extend(
415                    fold.nodes[stack[i]]
416                        .children
417                        .into_iter()
418                        .filter(|&v| v != u32::MAX)
419                        .map(|v| v as usize),
420                );
421                i += 1;
422            }
423            for &i in stack.iter().rev() {
424                fold.pull(i);
425            }
426            start = end;
427        }
428        fold
429    }
Source

pub fn is_empty(&self) -> bool

Source

pub fn root(&self) -> usize

Source

pub fn parent(&self, v: usize) -> Option<usize>

Source

pub fn index(&self, v: usize) -> usize

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 461)
460    pub fn set(&mut self, vertex: usize, value: M::T) {
461        let mut i = self.tree.index(vertex);
462        self.nodes[i].value = value;
463        while i != usize::MAX {
464            self.pull(i);
465            i = if self.nodes[i].parent == u32::MAX {
466                usize::MAX
467            } else {
468                self.nodes[i].parent as usize
469            };
470        }
471    }
472
473    fn fold_prefix<const REVERSE: bool>(&self, k: usize) -> M::T {
474        let mut result = M::unit();
475        let mut i = k;
476        while i != usize::MAX {
477            if i <= k {
478                result = if REVERSE {
479                    M::operate(&result, &self.nodes[i].prefix[1])
480                } else {
481                    M::operate(&self.nodes[i].prefix[0], &result)
482                };
483            }
484            i = if self.nodes[i].parent == u32::MAX {
485                usize::MAX
486            } else {
487                self.nodes[i].parent as usize
488            };
489        }
490        result
491    }
492
493    fn fold_range<const REVERSE: bool>(&self, l: usize, r: usize) -> M::T {
494        let (mut u, mut v) = (l, r);
495        let (mut left, mut right) = (M::unit(), M::unit());
496        while u != v {
497            if self.nodes[u].priority < self.nodes[v].priority {
498                if u >= l {
499                    let child = self.nodes[u].children[1];
500                    if REVERSE {
501                        left = M::operate(&self.nodes[u].value, &left);
502                        if child != u32::MAX {
503                            left = M::operate(&self.nodes[child as usize].aggregate[1], &left);
504                        }
505                    } else {
506                        left = M::operate(&left, &self.nodes[u].value);
507                        if child != u32::MAX {
508                            left = M::operate(&left, &self.nodes[child as usize].aggregate[0]);
509                        }
510                    }
511                }
512                u = self.nodes[u].parent as usize;
513            } else {
514                if v <= r {
515                    right = if REVERSE {
516                        M::operate(&right, &self.nodes[v].prefix[1])
517                    } else {
518                        M::operate(&self.nodes[v].prefix[0], &right)
519                    };
520                }
521                v = self.nodes[v].parent as usize;
522            }
523        }
524        if REVERSE {
525            M::operate(&M::operate(&right, &self.nodes[u].value), &left)
526        } else {
527            M::operate(&M::operate(&left, &self.nodes[u].value), &right)
528        }
529    }
530
531    /// Folds the vertex values in `u`-to-`v` order.
532    #[inline(always)]
533    pub fn fold_vertices(&self, mut u: usize, mut v: usize) -> M::T {
534        let (mut left, mut right) = (M::unit(), M::unit());
535        while self.tree.nodes[u].head != self.tree.nodes[v].head {
536            if self.tree.index(u) > self.tree.index(v) {
537                left = M::operate(&left, &self.fold_prefix::<true>(self.tree.index(u)));
538                u = self.tree.nodes[u].parent as usize;
539            } else {
540                right = M::operate(&self.fold_prefix::<false>(self.tree.index(v)), &right);
541                v = self.tree.nodes[v].parent as usize;
542            }
543        }
544        let middle = if self.tree.index(u) > self.tree.index(v) {
545            self.fold_range::<true>(self.tree.index(v), self.tree.index(u))
546        } else {
547            self.fold_range::<false>(self.tree.index(u), self.tree.index(v))
548        };
549        M::operate(&M::operate(&left, &middle), &right)
550    }
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 46)
38pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
41    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
42    let tree = UndirectedSparseGraph::from_edges(n, edges);
43    let hld = tree.hld(0);
44    let mut b = vec![0; n];
45    for (v, x) in a.into_iter().enumerate() {
46        b[hld.index(v)] = x;
47    }
48    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
49    for _ in 0..q {
50        sc!(query: Query);
51        match query {
52            Query::Add { u, x } => seg.update(hld.index(u), x),
53            Query::Sum { u } => {
54                pp!(seg.fold(hld.subtree_range(u)));
55            }
56        }
57    }
58}
Source

pub fn vertex(&self, index: usize) -> usize

Source

pub fn subtree_size(&self, v: usize) -> usize

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 383)
355    pub fn build_fold<M: Monoid>(&self, values: &[M::T]) -> HeavyLightPathFold<'_, M> {
356        assert_eq!(values.len(), self.len());
357        let mut fold = HeavyLightPathFold {
358            tree: self,
359            nodes: self
360                .order
361                .iter()
362                .map(|&v| PathFoldNode {
363                    parent: u32::MAX,
364                    children: [u32::MAX; 2],
365                    priority: 0,
366                    value: values[v].clone(),
367                    aggregate: [values[v].clone(), values[v].clone()],
368                    prefix: [values[v].clone(), values[v].clone()],
369                })
370                .collect(),
371        };
372        let mut start = 0;
373        let mut priorities = Vec::new();
374        let mut stack = Vec::new();
375        while start < self.len() {
376            let mut end = start + 1;
377            while end < self.len() && self.nodes[self.order[end]].head as usize == start {
378                end += 1;
379            }
380            priorities.clear();
381            let mut sum = 0usize;
382            for i in start..end {
383                let weight = self.subtree_size(self.order[i])
384                    - if i + 1 < end {
385                        self.subtree_size(self.order[i + 1])
386                    } else {
387                        0
388                    };
389                let priority = (sum ^ (sum + weight)).ilog2();
390                sum += weight;
391                fold.nodes[i].priority = priority;
392                priorities.push(std::cmp::Reverse(priority));
393            }
394            let cartesian = CartesianTree::new(&priorities);
395            for i in start..end {
396                let parent = cartesian.parents[i - start];
397                fold.nodes[i].parent = if parent == usize::MAX {
398                    u32::MAX
399                } else {
400                    (parent + start) as u32
401                };
402                fold.nodes[i].children = cartesian.children[i - start].map(|v| {
403                    if v == usize::MAX {
404                        u32::MAX
405                    } else {
406                        (v + start) as u32
407                    }
408                });
409            }
410            stack.clear();
411            stack.push(cartesian.root + start);
412            let mut i = 0;
413            while i < stack.len() {
414                stack.extend(
415                    fold.nodes[stack[i]]
416                        .children
417                        .into_iter()
418                        .filter(|&v| v != u32::MAX)
419                        .map(|v| v as usize),
420                );
421                i += 1;
422            }
423            for &i in stack.iter().rev() {
424                fold.pull(i);
425            }
426            start = end;
427        }
428        fold
429    }
Source

pub fn subtree_range(&self, v: usize) -> Range<usize> ⓘ

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 129)
128    pub fn is_ancestor(&self, ancestor: usize, v: usize) -> bool {
129        self.subtree_range(ancestor)
130            .contains(&(self.nodes[v].index as usize))
131    }
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 54)
38pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
41    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
42    let tree = UndirectedSparseGraph::from_edges(n, edges);
43    let hld = tree.hld(0);
44    let mut b = vec![0; n];
45    for (v, x) in a.into_iter().enumerate() {
46        b[hld.index(v)] = x;
47    }
48    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
49    for _ in 0..q {
50        sc!(query: Query);
51        match query {
52            Query::Add { u, x } => seg.update(hld.index(u), x),
53            Query::Sum { u } => {
54                pp!(seg.fold(hld.subtree_range(u)));
55            }
56        }
57    }
58}
Source

pub fn is_ancestor(&self, ancestor: usize, v: usize) -> bool

Source

pub fn kth_ancestor(&self, v: usize, k: usize) -> Option<usize>

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 198)
172    pub fn jump(&self, mut u: usize, mut v: usize, mut k: usize) -> Option<usize> {
173        let target = v;
174        let mut down = 0;
175        while self.nodes[u].head != self.nodes[v].head {
176            if self.nodes[u].index > self.nodes[v].index {
177                let up = self.nodes[u].index as usize - self.nodes[u].head as usize + 1;
178                if k < up {
179                    return Some(self.order[self.nodes[u].index as usize - k]);
180                }
181                k -= up;
182                u = self.nodes[u].parent as usize;
183            } else {
184                down += self.nodes[v].index as usize - self.nodes[v].head as usize + 1;
185                v = self.nodes[v].parent as usize;
186            }
187        }
188        if self.nodes[u].index >= self.nodes[v].index {
189            let up = self.nodes[u].index as usize - self.nodes[v].index as usize;
190            if k <= up {
191                return Some(self.order[self.nodes[u].index as usize - k]);
192            }
193            k -= up;
194        } else {
195            down += self.nodes[v].index as usize - self.nodes[u].index as usize;
196        }
197        down.checked_sub(k)
198            .and_then(|k| self.kth_ancestor(target, k))
199    }
Source

pub fn lca(&self, u: usize, v: usize) -> usize

Examples found in repository?
crates/library_checker/src/tree/lca.rs (line 27)
19pub fn lca_hld(reader: impl Read, writer: impl Write) {
20    prepare_io!(reader, writer);
21    sc!(n, q, p: [usize; iter n - 1]);
22    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
23    let graph = UndirectedSparseGraph::from_edges(n, edges);
24    let hld = graph.hld(0);
25    for _ in 0..q {
26        sc!(u, v);
27        pp!(hld.lca(u, v));
28    }
29}
Source

pub fn distance(&self, u: usize, v: usize) -> usize

Source

pub fn jump(&self, u: usize, v: usize, k: usize) -> Option<usize>

Examples found in repository?
crates/library_checker/src/tree/jump_on_tree.rs (line 11)
5pub fn jump_on_tree(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, (g, _): @TreeGraphScanner::<usize>::new(n));
8    let hld = g.hld(0);
9    for _ in 0..q {
10        sc!(s, t, i);
11        pp!(hld.jump(s, t, i).unwrap_or(!0) as isize);
12    }
13}
Source

fn path_lengths(&self, u: usize, v: usize) -> (usize, usize)

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 167)
166    pub fn distance(&self, u: usize, v: usize) -> usize {
167        let (up, down) = self.path_lengths(u, v);
168        up + down
169    }
Source

pub fn path_vertices<F: FnMut(usize, usize)>(&self, u: usize, v: usize, f: F)

Calls f once for each nonempty DFS-index range on the vertex path. The callback order is unspecified.

Source

pub fn path_edges<F: FnMut(usize, usize)>(&self, u: usize, v: usize, f: F)

Calls f once for each nonempty DFS-index range on the edge path. Each index represents the deeper endpoint of an edge. The callback order is unspecified.

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_5_e.rs (line 31)
15pub fn grl_5_e(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let hld = graph.hld(0);
24    let mut seg = LazySegmentTree::<RangeSumRangeAdd<_>>::from_keys(std::iter::repeat_n(0u64, n));
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                hld.path_edges(0, v, |l, r| seg.update(l..r, w));
32            }
33            Query::Get { u } => {
34                let mut ans = 0;
35                hld.path_edges(0, u, |l, r| ans += seg.fold(l..r).0);
36                pp!(ans);
37            }
38        }
39    }
40}
Source

fn path<F: FnMut(usize, usize)>(&self, u: usize, v: usize, is_edge: bool, f: F)

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 225)
224    pub fn path_vertices<F: FnMut(usize, usize)>(&self, u: usize, v: usize, f: F) {
225        self.path(u, v, false, f);
226    }
227
228    /// Calls `f` once for each nonempty DFS-index range on the edge path.
229    /// Each index represents the deeper endpoint of an edge. The callback order is unspecified.
230    #[inline]
231    pub fn path_edges<F: FnMut(usize, usize)>(&self, u: usize, v: usize, f: F) {
232        self.path(u, v, true, f);
233    }
Source

pub fn fold_vertices<M: Monoid, F1: FnMut(usize, usize) -> M::T, F2: FnMut(usize, usize) -> M::T>( &self, u: usize, v: usize, forward: F1, reverse: F2, ) -> M::T

Folds a vertex path in u-to-v order. forward folds a DFS-index range from left to right, and reverse folds it from right to left.

Source

pub fn fold_edges<M: Monoid, F1: FnMut(usize, usize) -> M::T, F2: FnMut(usize, usize) -> M::T>( &self, u: usize, v: usize, forward: F1, reverse: F2, ) -> M::T

Folds an edge path in u-to-v order. Each index represents the deeper endpoint of an edge. forward folds a DFS-index range from left to right, and reverse folds it from right to left.

Source

fn fold<M: Monoid, F1: FnMut(usize, usize) -> M::T, F2: FnMut(usize, usize) -> M::T>( &self, u: usize, v: usize, is_edge: bool, forward: F1, reverse: F2, ) -> M::T

Examples found in repository?
crates/competitive/src/tree/heavy_light_decomposition.rs (line 272)
261    pub fn fold_vertices<
262        M: Monoid,
263        F1: FnMut(usize, usize) -> M::T,
264        F2: FnMut(usize, usize) -> M::T,
265    >(
266        &self,
267        u: usize,
268        v: usize,
269        forward: F1,
270        reverse: F2,
271    ) -> M::T {
272        self.fold::<M, _, _>(u, v, false, forward, reverse)
273    }
274
275    /// Folds an edge path in `u`-to-`v` order.
276    /// Each index represents the deeper endpoint of an edge. `forward` folds a DFS-index range
277    /// from left to right, and `reverse` folds it from right to left.
278    #[inline]
279    pub fn fold_edges<
280        M: Monoid,
281        F1: FnMut(usize, usize) -> M::T,
282        F2: FnMut(usize, usize) -> M::T,
283    >(
284        &self,
285        u: usize,
286        v: usize,
287        forward: F1,
288        reverse: F2,
289    ) -> M::T {
290        self.fold::<M, _, _>(u, v, true, forward, reverse)
291    }
Source§

impl HeavyLightDecomposition

Source

pub fn build_fold<M: Monoid>( &self, values: &[M::T], ) -> HeavyLightPathFold<'_, M>

values is indexed by vertex, not by DFS index.

Examples found in repository?
crates/library_checker/src/tree/vertex_set_path_composite.rs (line 18)
14pub fn vertex_set_path_composite(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, ab: [(M, M); n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let hld = graph.hld(0);
18    let mut fold = hld.build_fold::<LinearOperation<_>>(&ab);
19    for _ in 0..q {
20        sc!(query: Query);
21        match query {
22            Query::Set { p, cd } => {
23                fold.set(p, cd);
24            }
25            Query::Apply { u, v, x } => {
26                let (a, b) = fold.fold_vertices(u, v);
27                pp!(a * x + b);
28            }
29        }
30    }
31}

Trait Implementations§

Source§

impl Clone for HeavyLightDecomposition

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for HeavyLightDecomposition

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.