competitive::tree::centroid_decomposition

Struct RootedTree

struct RootedTree {
    parents: Vec<usize>,
    vs: Vec<usize>,
}

Fields§

§parents: Vec<usize>§vs: Vec<usize>

Implementations§

Source §

impl RootedTree

Source

fn len(&self) -> usize

Examples found in repository ?

crates/competitive/src/tree/centroid_decomposition.rs (line 16)

15    fn split_centroid(self) -> CentroidSplit {
16        let n = self.len();
17        assert!(n > 2);
18        let parents = &self.parents;
19        let vs = &self.vs;
20        let mut size = vec![1; n];
21        let mut c = usize::MAX;
22        for i in (0..n).rev() {
23            if size[i] >= n.div_ceil(2) {
24                c = i;
25                break;
26            }
27            size[parents[i]] += size[i];
28        }
29        let mut side = vec![u8::MAX; n];
30        let mut order = vec![usize::MAX; n];
31        order[c] = 0;
32        let mut count = 1usize;
33        let mut taken = 0usize;
34        for u in 1..n {
35            if parents[u] == c && taken + size[u] <= (n - 1) / 2 {
36                taken += size[u];
37                side[u] = 0;
38                order[u] = count;
39                count += 1;
40            }
41        }
42        for u in 1..n {
43            if side[parents[u]] == 0 {
44                side[u] = 0;
45                order[u] = count;
46                count += 1;
47            }
48        }
49        let lsize = count - 1;
50        {
51            let mut u = parents[c];
52            while u != usize::MAX {
53                side[u] = 1;
54                order[u] = count;
55                count += 1;
56                u = parents[u];
57            }
58        }
59        for u in 0..n {
60            if u != c && side[u] == u8::MAX {
61                side[u] = 1;
62                order[u] = count;
63                count += 1;
64            }
65        }
66        assert_eq!(count, n);
67        let mut whole_parents = vec![usize::MAX; n];
68        let mut whole_vs = vec![usize::MAX; n];
69        for u in 0..n {
70            whole_vs[order[u]] = vs[u];
71        }
72        for u in 1..n {
73            let mut x = order[u];
74            let mut y = order[parents[u]];
75            if x > y {
76                swap(&mut x, &mut y);
77            }
78            whole_parents[y] = x;
79        }
80        let left = RootedTree {
81            parents: whole_parents[..=lsize].to_vec(),
82            vs: whole_vs[..=lsize].to_vec(),
83        };
84        let right = RootedTree {
85            parents: std::iter::once(usize::MAX)
86                .chain(
87                    whole_parents[lsize + 1..]
88                        .iter()
89                        .map(|&p| if p == 0 { 0 } else { p - lsize }),
90                )
91                .collect(),
92            vs: std::iter::once(whole_vs[0])
93                .chain(whole_vs[lsize + 1..].iter().copied())
94                .collect(),
95        };
96        CentroidSplit {
97            whole: RootedTree {
98                parents: whole_parents,
99                vs: whole_vs,
100            },
101            left,
102            right,
103            lsize,
104        }
105    }
106
107    fn centroid_decomposition(self, f: &mut impl FnMut(&[usize], &[usize], usize, usize)) {
108        if self.len() <= 2 {
109            return;
110        }
111        let split = self.split_centroid();
112        f(
113            &split.whole.parents,
114            &split.whole.vs,
115            split.lsize,
116            split.rsize(),
117        );
118        split.left.centroid_decomposition(f);
119        split.right.centroid_decomposition(f);
120    }
121}
122
123impl From<&UndirectedSparseGraph> for RootedTree {
124    fn from(graph: &UndirectedSparseGraph) -> Self {
125        let n = graph.vertices_size();
126        let mut vs = Vec::with_capacity(n);
127        let mut parent = vec![usize::MAX; n];
128        vs.push(0usize);
129        for i in 0..n {
130            let u = vs[i];
131            for a in graph.neighbors(u) {
132                if a.to != parent[u] {
133                    vs.push(a.to);
134                    parent[a.to] = u;
135                }
136            }
137        }
138        let mut new_idx = vec![0; n];
139        for (i, &v) in vs.iter().enumerate() {
140            new_idx[v] = i;
141        }
142        let mut parents = vec![usize::MAX; n];
143        for v in 1..n {
144            parents[new_idx[v]] = new_idx[parent[v]];
145        }
146        Self { parents, vs }
147    }
148}
149
150#[derive(Debug)]
151struct CentroidSplit {
152    whole: RootedTree,
153    left: RootedTree,
154    right: RootedTree,
155    lsize: usize,
156}
157
158impl CentroidSplit {
159    fn rsize(&self) -> usize {
160        self.whole.len() - self.lsize - 1
161    }

Source

fn split_centroid(self) -> CentroidSplit

Examples found in repository ?

crates/competitive/src/tree/centroid_decomposition.rs (line 111)

107    fn centroid_decomposition(self, f: &mut impl FnMut(&[usize], &[usize], usize, usize)) {
108        if self.len() <= 2 {
109            return;
110        }
111        let split = self.split_centroid();
112        f(
113            &split.whole.parents,
114            &split.whole.vs,
115            split.lsize,
116            split.rsize(),
117        );
118        split.left.centroid_decomposition(f);
119        split.right.centroid_decomposition(f);
120    }

Source

fn centroid_decomposition( self, f: &mut impl FnMut(&[usize], &[usize], usize, usize), )

Examples found in repository ?

crates/competitive/src/tree/centroid_decomposition.rs (line 118)

107    fn centroid_decomposition(self, f: &mut impl FnMut(&[usize], &[usize], usize, usize)) {
108        if self.len() <= 2 {
109            return;
110        }
111        let split = self.split_centroid();
112        f(
113            &split.whole.parents,
114            &split.whole.vs,
115            split.lsize,
116            split.rsize(),
117        );
118        split.left.centroid_decomposition(f);
119        split.right.centroid_decomposition(f);
120    }
121}
122
123impl From<&UndirectedSparseGraph> for RootedTree {
124    fn from(graph: &UndirectedSparseGraph) -> Self {
125        let n = graph.vertices_size();
126        let mut vs = Vec::with_capacity(n);
127        let mut parent = vec![usize::MAX; n];
128        vs.push(0usize);
129        for i in 0..n {
130            let u = vs[i];
131            for a in graph.neighbors(u) {
132                if a.to != parent[u] {
133                    vs.push(a.to);
134                    parent[a.to] = u;
135                }
136            }
137        }
138        let mut new_idx = vec![0; n];
139        for (i, &v) in vs.iter().enumerate() {
140            new_idx[v] = i;
141        }
142        let mut parents = vec![usize::MAX; n];
143        for v in 1..n {
144            parents[new_idx[v]] = new_idx[parent[v]];
145        }
146        Self { parents, vs }
147    }
148}
149
150#[derive(Debug)]
151struct CentroidSplit {
152    whole: RootedTree,
153    left: RootedTree,
154    right: RootedTree,
155    lsize: usize,
156}
157
158impl CentroidSplit {
159    fn rsize(&self) -> usize {
160        self.whole.len() - self.lsize - 1
161    }
162}
163
164#[derive(Debug, Clone, Copy)]
165struct ContourInfo {
166    comp: u32,
167    dep: u32,
168}
169
170#[derive(Debug, Clone)]
171pub struct ContourQueryRange {
172    comp_range: Vec<usize>,
173    info_indptr: Vec<usize>,
174    infos: Vec<ContourInfo>,
175    local_info: Vec<(usize, usize)>,
176    local_offsets: Vec<usize>,
177    local_masks: Vec<u32>,
178}
179
180impl ContourQueryRange {
181    pub fn len(&self) -> usize {
182        self.comp_range.last().copied().unwrap_or_default()
183    }
184
185    pub fn is_empty(&self) -> bool {
186        self.len() == 0
187    }
188
189    pub fn component_sizes(&self) -> impl ExactSizeIterator<Item = usize> + '_ {
190        self.comp_range.windows(2).map(|range| range[1] - range[0])
191    }
192
193    /// Calls `f(component, index)` for each position representing `v`.
194    pub fn for_each_index(&self, v: usize, mut f: impl FnMut(usize, usize)) {
195        for info in &self.infos[self.info_indptr[v]..self.info_indptr[v + 1]] {
196            f(info.comp as usize, info.dep as usize);
197        }
198        let (comp, index) = self.local_info[v];
199        if comp != usize::MAX {
200            f(
201                self.comp_range.len() - 1 - self.local_offsets.len() + comp,
202                index,
203            );
204        }
205    }
206
207    /// Calls `f(component, start, end)` for disjoint ranges at distances in `l..r` from `v`.
208    /// The ranges exclude `v` itself, even when `l == 0`.
209    pub fn for_each_contour_range(
210        &self,
211        v: usize,
212        l: usize,
213        r: usize,
214        mut f: impl FnMut(usize, usize, usize),
215    ) {
216        for info in &self.infos[self.info_indptr[v]..self.info_indptr[v + 1]] {
217            let comp = (info.comp ^ 1) as usize;
218            let start = self.comp_range[comp];
219            let len = self.comp_range[comp + 1] - start;
220            let lo = l.saturating_sub(info.dep as usize).min(len);
221            let hi = r.saturating_sub(info.dep as usize).min(len);
222            if lo < hi {
223                f(comp, lo, hi);
224            }
225        }
226        let (local, index) = self.local_info[v];
227        if local != usize::MAX {
228            let comp = self.comp_range.len() - 1 - self.local_offsets.len() + local;
229            let len = self.comp_range[comp + 1] - self.comp_range[comp];
230            let lo = l.max(1).min(len);
231            let hi = r.min(len);
232            if lo < hi {
233                let offset = self.local_offsets[local] + index * (len + 1);
234                let mut mask = self.local_masks[offset + hi] ^ self.local_masks[offset + lo];
235                while mask != 0 {
236                    let start = mask.trailing_zeros();
237                    let end = start + (mask >> start).trailing_ones();
238                    f(comp, start as usize, end as usize);
239                    mask &= mask.wrapping_add(1 << start);
240                }
241            }
242        }
243    }
244}
245
246impl UndirectedSparseGraph {
247    /// 1/3 centroid decomposition
248    ///
249    /// - f: (parents: &[usize], vs: &[usize], lsize: usize, rsize: usize)
250    /// - 0: root, 1..=lsize: left subtree, lsize+1..=lsize+rsize: right subtree
251    pub fn centroid_decomposition(&self, mut f: impl FnMut(&[usize], &[usize], usize, usize)) {
252        if self.vertices_size() <= 1 {
253            return;
254        }
255        RootedTree::from(self).centroid_decomposition(&mut f);
256    }