competitive::tree::centroid_decomposition

Struct CentroidSplit

struct CentroidSplit {
    whole: RootedTree,
    left: RootedTree,
    right: RootedTree,
    old_to_new: Vec<usize>,
    lsize: usize,
}

Fields§

§whole: RootedTree§left: RootedTree§right: RootedTree§old_to_new: Vec<usize>§lsize: usize

Implementations§

Source §

impl CentroidSplit

Source

fn rsize(&self) -> usize

Examples found in repository ?

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

117    fn centroid_decomposition(self, f: &mut impl FnMut(&[usize], &[usize], usize, usize)) {
118        if self.len() <= 2 {
119            return;
120        }
121        let split = self.split_centroid();
122        f(
123            &split.whole.parents,
124            &split.whole.vs,
125            split.lsize,
126            split.rsize(),
127        );
128        split.left.centroid_decomposition(f);
129        split.right.centroid_decomposition(f);
130    }
131
132    fn append_contour_components(
133        &self,
134        color: &[i8],
135        comp_range: &mut Vec<usize>,
136        vertex_info: &mut [Vec<ContourInfo>],
137    ) {
138        let n = self.len();
139        let mut dist = vec![0usize; n];
140        for i in 1..n {
141            dist[i] = dist[self.parents[i]] + 1;
142        }
143        let mut comp = comp_range.len() - 1;
144        for c1 in [0, 1] {
145            let mut max_a = 0usize;
146            let mut max_b = 0usize;
147            let mut has_a = false;
148            let mut has_b = false;
149            for (v, &c2) in color.iter().enumerate() {
150                if c2 == c1 {
151                    has_a = true;
152                    max_a = max_a.max(dist[v]);
153                } else if c2 > c1 {
154                    has_b = true;
155                    max_b = max_b.max(dist[v]);
156                }
157            }
158            if !has_a || !has_b {
159                continue;
160            }
161            for (v, &c2) in color.iter().enumerate() {
162                if c2 == c1 {
163                    vertex_info[self.vs[v]].push(ContourInfo { comp, dep: dist[v] });
164                }
165            }
166            comp_range.push(comp_range[comp] + max_a + 1);
167            comp += 1;
168            for (v, &c2) in color.iter().enumerate() {
169                if c2 > c1 {
170                    vertex_info[self.vs[v]].push(ContourInfo { comp, dep: dist[v] });
171                }
172            }
173            comp_range.push(comp_range[comp] + max_b + 1);
174            comp += 1;
175        }
176    }
177
178    fn build_contour_query_range(
179        self,
180        real: Vec<bool>,
181        comp_range: &mut Vec<usize>,
182        vertex_info: &mut [Vec<ContourInfo>],
183    ) {
184        let n = self.len();
185        if n <= 1 {
186            return;
187        }
188        if n == 2 {
189            if real[0] && real[1] {
190                self.append_contour_components(&[0, 1], comp_range, vertex_info);
191            }
192            return;
193        }
194        let split = self.split_centroid();
195        let mut whole_real = vec![false; n];
196        for (u, &is_real) in real.iter().enumerate() {
197            if is_real {
198                whole_real[split.old_to_new[u]] = true;
199            }
200        }
201        let mut color = vec![-1i8; n];
202        for (i, &is_real) in whole_real.iter().enumerate().skip(1) {
203            if is_real {
204                color[i] = if i <= split.lsize { 0 } else { 1 };
205            }
206        }
207        if whole_real[0] {
208            color[0] = 2;
209        }
210        split
211            .whole
212            .append_contour_components(&color, comp_range, vertex_info);
213        if whole_real[0] {
214            whole_real[0] = false;
215        }
216        let mut right_real = Vec::with_capacity(split.rsize() + 1);
217        right_real.push(whole_real[0]);
218        right_real.extend_from_slice(&whole_real[split.lsize + 1..]);
219        split.left.build_contour_query_range(
220            whole_real[..=split.lsize].to_vec(),
221            comp_range,
222            vertex_info,
223        );
224        split
225            .right
226            .build_contour_query_range(right_real, comp_range, vertex_info);
227    }