Skip to main content

StaticTopTree

competitive::tree::static_top_tree

Struct StaticTopTree 

Source 
pub struct StaticTopTree {
    root: usize,
    n: usize,
    edge_child: Vec<usize>,
    parent_edge: Vec<usize>,
    compressed: Vec<InnerNode>,
    raked: Vec<InnerNode>,
    vertex_links: Vec<VertexLinks>,
    compress_roots: Vec<Option<Slot>>,
    rake_roots: Vec<Option<Slot>>,
}

Fields§

§root: usize§n: usize§edge_child: Vec<usize>§parent_edge: Vec<usize>§compressed: Vec<InnerNode>§raked: Vec<InnerNode>§vertex_links: Vec<VertexLinks>§compress_roots: Vec<Option<Slot>>§rake_roots: Vec<Option<Slot>>

Implementations§

Source§

impl StaticTopTree

Source

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

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 151)
150    pub fn static_top_tree(&self, root: usize) -> StaticTopTree {
151        StaticTopTree::new(root, self)
152    }
Source

pub fn vertices_size(&self) -> usize

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 287)
279    pub fn fold_all<C>(
280        &self,
281        vertices: &[<C as Cluster>::Vertex],
282        edges: &[<C as Cluster>::Edge],
283    ) -> <C as Cluster>::Point
284    where
285        C: Cluster,
286    {
287        assert_eq!(vertices.len(), self.vertices_size());
288        assert_eq!(edges.len(), self.edges_size());
289        let path = self.fold_compress::<C>(
290            vertices,
291            edges,
292            self.compress_roots[self.root].expect("root compress tree must exist"),
293        );
294        C::add_edge(&path)
295    }
296
297    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
298        let start = vertex;
299        let mut stack = Vec::new();
300        while vertex != usize::MAX {
301            stack.push(Node {
302                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
303                slot: Slot::CompressLeaf(vertex),
304            });
305            loop {
306                let len = stack.len();
307                if len >= 3
308                    && (stack[len - 3].depth == stack[len - 2].depth
309                        || stack[len - 3].depth <= stack[len - 1].depth)
310                {
311                    let tail = stack.pop().unwrap();
312                    let right = stack.pop().unwrap();
313                    let left = stack.pop().unwrap();
314                    let node = self.merge_compress(left, right);
315                    stack.push(node);
316                    stack.push(tail);
317                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
318                    let right = stack.pop().unwrap();
319                    let left = stack.pop().unwrap();
320                    stack.push(self.merge_compress(left, right));
321                } else {
322                    break;
323                }
324            }
325            vertex = heavy_child[vertex];
326        }
327        while stack.len() > 1 {
328            let right = stack.pop().unwrap();
329            let left = stack.pop().unwrap();
330            stack.push(self.merge_compress(left, right));
331        }
332        let root = stack.pop().unwrap();
333        self.compress_roots[start] = Some(root.slot);
334        root
335    }
336
337    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
338        let id = self.compressed.len();
339        self.set_parent(left.slot, id << 1);
340        self.set_parent(right.slot, id << 1 | 1);
341        self.compressed.push(InnerNode {
342            left: left.slot,
343            right: right.slot,
344            parent: usize::MAX,
345        });
346        Node {
347            depth: left.depth.max(right.depth) + 1,
348            slot: Slot::CompressInner(id),
349        }
350    }
351
352    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
353        let id = self.raked.len();
354        self.set_parent(left.slot, id << 1);
355        self.set_parent(right.slot, id << 1 | 1);
356        self.raked.push(InnerNode {
357            left: left.slot,
358            right: right.slot,
359            parent: usize::MAX,
360        });
361        Node {
362            depth: left.depth.max(right.depth) + 1,
363            slot: Slot::RakeInner(id),
364        }
365    }
366
367    fn set_parent(&mut self, slot: Slot, parent: usize) {
368        match slot {
369            Slot::CompressLeaf(v) => self.vertex_links[v].compress_parent = parent,
370            Slot::CompressInner(i) => self.compressed[i].parent = parent,
371            Slot::RakeLeaf(v) => self.vertex_links[v].rake_parent = parent,
372            Slot::RakeInner(i) => self.raked[i].parent = parent,
373        }
374    }
375
376    fn init_compress<C>(
377        &self,
378        data: &mut StaticTopTreeDataBuilder<C>,
379        vertices: &[<C as Cluster>::Vertex],
380        edges: &[<C as Cluster>::Edge],
381        slot: Slot,
382    ) -> <C as Cluster>::Path
383    where
384        C: Cluster,
385    {
386        match slot {
387            Slot::CompressLeaf(vertex) => {
388                let point = self.init_point(data, vertices, edges, vertex);
389                C::add_vertex(
390                    &point,
391                    &vertices[vertex],
392                    self.parent_edge_ref(edges, vertex),
393                )
394            }
395            Slot::CompressInner(id) => {
396                let node = &self.compressed[id];
397                let left = self.init_compress(data, vertices, edges, node.left);
398                let right = self.init_compress(data, vertices, edges, node.right);
399                data.compressed[id].write(InnerValue {
400                    parent: node.parent,
401                    left: left.clone(),
402                    right: right.clone(),
403                });
404                C::compress(&left, &right)
405            }
406            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
407        }
408    }
409
410    fn fold_compress<C>(
411        &self,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Path
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::CompressLeaf(vertex) => {
421                let point = self.fold_point::<C>(vertices, edges, vertex);
422                C::add_vertex(
423                    &point,
424                    &vertices[vertex],
425                    self.parent_edge_ref(edges, vertex),
426                )
427            }
428            Slot::CompressInner(id) => {
429                let node = &self.compressed[id];
430                let left = self.fold_compress::<C>(vertices, edges, node.left);
431                let right = self.fold_compress::<C>(vertices, edges, node.right);
432                C::compress(&left, &right)
433            }
434            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
435        }
436    }
437
438    fn init_point<C>(
439        &self,
440        data: &mut StaticTopTreeDataBuilder<C>,
441        vertices: &[<C as Cluster>::Vertex],
442        edges: &[<C as Cluster>::Edge],
443        vertex: usize,
444    ) -> <C as Cluster>::Point
445    where
446        C: Cluster,
447    {
448        let point = if let Some(slot) = self.rake_roots[vertex] {
449            self.init_rake(data, vertices, edges, slot)
450        } else {
451            C::unit_point()
452        };
453        data.light_points[vertex] = point.clone();
454        point
455    }
456
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
507
508    fn fold_rake<C>(
509        &self,
510        vertices: &[<C as Cluster>::Vertex],
511        edges: &[<C as Cluster>::Edge],
512        slot: Slot,
513    ) -> <C as Cluster>::Point
514    where
515        C: Cluster,
516    {
517        match slot {
518            Slot::RakeLeaf(vertex) => {
519                let path = self.fold_compress::<C>(
520                    vertices,
521                    edges,
522                    self.compress_roots[vertex].expect("light child path must exist"),
523                );
524                C::add_edge(&path)
525            }
526            Slot::RakeInner(id) => {
527                let node = &self.raked[id];
528                let left = self.fold_rake::<C>(vertices, edges, node.left);
529                let right = self.fold_rake::<C>(vertices, edges, node.right);
530                C::rake(&left, &right)
531            }
532            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
533        }
534    }
535
536    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
537        let edge = self.parent_edge[vertex];
538        if edge == usize::MAX {
539            None
540        } else {
541            Some(&edges[edge])
542        }
543    }
544}
545
546impl<'a, C> StaticTopTreeDp<'a, C>
547where
548    C: Cluster,
549{
550    pub fn new(
551        tree: &'a StaticTopTree,
552        vertices: Vec<<C as Cluster>::Vertex>,
553        edges: Vec<<C as Cluster>::Edge>,
554    ) -> Self {
555        assert_eq!(vertices.len(), tree.vertices_size());
556        assert_eq!(edges.len(), tree.edges_size());
557
558        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
559        let path = tree.init_compress(
560            &mut data,
561            &vertices,
562            &edges,
563            tree.compress_roots[tree.root].expect("root compress tree must exist"),
564        );
565        let all_point = C::add_edge(&path);
566        Self {
567            tree,
568            vertices,
569            edges,
570            compressed: unsafe { assume_init_vec(data.compressed) },
571            raked: unsafe { assume_init_vec(data.raked) },
572            light_points: data.light_points,
573            all_point,
574        }
575    }
Source

pub fn edges_size(&self) -> usize

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 288)
279    pub fn fold_all<C>(
280        &self,
281        vertices: &[<C as Cluster>::Vertex],
282        edges: &[<C as Cluster>::Edge],
283    ) -> <C as Cluster>::Point
284    where
285        C: Cluster,
286    {
287        assert_eq!(vertices.len(), self.vertices_size());
288        assert_eq!(edges.len(), self.edges_size());
289        let path = self.fold_compress::<C>(
290            vertices,
291            edges,
292            self.compress_roots[self.root].expect("root compress tree must exist"),
293        );
294        C::add_edge(&path)
295    }
296
297    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
298        let start = vertex;
299        let mut stack = Vec::new();
300        while vertex != usize::MAX {
301            stack.push(Node {
302                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
303                slot: Slot::CompressLeaf(vertex),
304            });
305            loop {
306                let len = stack.len();
307                if len >= 3
308                    && (stack[len - 3].depth == stack[len - 2].depth
309                        || stack[len - 3].depth <= stack[len - 1].depth)
310                {
311                    let tail = stack.pop().unwrap();
312                    let right = stack.pop().unwrap();
313                    let left = stack.pop().unwrap();
314                    let node = self.merge_compress(left, right);
315                    stack.push(node);
316                    stack.push(tail);
317                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
318                    let right = stack.pop().unwrap();
319                    let left = stack.pop().unwrap();
320                    stack.push(self.merge_compress(left, right));
321                } else {
322                    break;
323                }
324            }
325            vertex = heavy_child[vertex];
326        }
327        while stack.len() > 1 {
328            let right = stack.pop().unwrap();
329            let left = stack.pop().unwrap();
330            stack.push(self.merge_compress(left, right));
331        }
332        let root = stack.pop().unwrap();
333        self.compress_roots[start] = Some(root.slot);
334        root
335    }
336
337    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
338        let id = self.compressed.len();
339        self.set_parent(left.slot, id << 1);
340        self.set_parent(right.slot, id << 1 | 1);
341        self.compressed.push(InnerNode {
342            left: left.slot,
343            right: right.slot,
344            parent: usize::MAX,
345        });
346        Node {
347            depth: left.depth.max(right.depth) + 1,
348            slot: Slot::CompressInner(id),
349        }
350    }
351
352    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
353        let id = self.raked.len();
354        self.set_parent(left.slot, id << 1);
355        self.set_parent(right.slot, id << 1 | 1);
356        self.raked.push(InnerNode {
357            left: left.slot,
358            right: right.slot,
359            parent: usize::MAX,
360        });
361        Node {
362            depth: left.depth.max(right.depth) + 1,
363            slot: Slot::RakeInner(id),
364        }
365    }
366
367    fn set_parent(&mut self, slot: Slot, parent: usize) {
368        match slot {
369            Slot::CompressLeaf(v) => self.vertex_links[v].compress_parent = parent,
370            Slot::CompressInner(i) => self.compressed[i].parent = parent,
371            Slot::RakeLeaf(v) => self.vertex_links[v].rake_parent = parent,
372            Slot::RakeInner(i) => self.raked[i].parent = parent,
373        }
374    }
375
376    fn init_compress<C>(
377        &self,
378        data: &mut StaticTopTreeDataBuilder<C>,
379        vertices: &[<C as Cluster>::Vertex],
380        edges: &[<C as Cluster>::Edge],
381        slot: Slot,
382    ) -> <C as Cluster>::Path
383    where
384        C: Cluster,
385    {
386        match slot {
387            Slot::CompressLeaf(vertex) => {
388                let point = self.init_point(data, vertices, edges, vertex);
389                C::add_vertex(
390                    &point,
391                    &vertices[vertex],
392                    self.parent_edge_ref(edges, vertex),
393                )
394            }
395            Slot::CompressInner(id) => {
396                let node = &self.compressed[id];
397                let left = self.init_compress(data, vertices, edges, node.left);
398                let right = self.init_compress(data, vertices, edges, node.right);
399                data.compressed[id].write(InnerValue {
400                    parent: node.parent,
401                    left: left.clone(),
402                    right: right.clone(),
403                });
404                C::compress(&left, &right)
405            }
406            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
407        }
408    }
409
410    fn fold_compress<C>(
411        &self,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Path
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::CompressLeaf(vertex) => {
421                let point = self.fold_point::<C>(vertices, edges, vertex);
422                C::add_vertex(
423                    &point,
424                    &vertices[vertex],
425                    self.parent_edge_ref(edges, vertex),
426                )
427            }
428            Slot::CompressInner(id) => {
429                let node = &self.compressed[id];
430                let left = self.fold_compress::<C>(vertices, edges, node.left);
431                let right = self.fold_compress::<C>(vertices, edges, node.right);
432                C::compress(&left, &right)
433            }
434            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
435        }
436    }
437
438    fn init_point<C>(
439        &self,
440        data: &mut StaticTopTreeDataBuilder<C>,
441        vertices: &[<C as Cluster>::Vertex],
442        edges: &[<C as Cluster>::Edge],
443        vertex: usize,
444    ) -> <C as Cluster>::Point
445    where
446        C: Cluster,
447    {
448        let point = if let Some(slot) = self.rake_roots[vertex] {
449            self.init_rake(data, vertices, edges, slot)
450        } else {
451            C::unit_point()
452        };
453        data.light_points[vertex] = point.clone();
454        point
455    }
456
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
507
508    fn fold_rake<C>(
509        &self,
510        vertices: &[<C as Cluster>::Vertex],
511        edges: &[<C as Cluster>::Edge],
512        slot: Slot,
513    ) -> <C as Cluster>::Point
514    where
515        C: Cluster,
516    {
517        match slot {
518            Slot::RakeLeaf(vertex) => {
519                let path = self.fold_compress::<C>(
520                    vertices,
521                    edges,
522                    self.compress_roots[vertex].expect("light child path must exist"),
523                );
524                C::add_edge(&path)
525            }
526            Slot::RakeInner(id) => {
527                let node = &self.raked[id];
528                let left = self.fold_rake::<C>(vertices, edges, node.left);
529                let right = self.fold_rake::<C>(vertices, edges, node.right);
530                C::rake(&left, &right)
531            }
532            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
533        }
534    }
535
536    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
537        let edge = self.parent_edge[vertex];
538        if edge == usize::MAX {
539            None
540        } else {
541            Some(&edges[edge])
542        }
543    }
544}
545
546impl<'a, C> StaticTopTreeDp<'a, C>
547where
548    C: Cluster,
549{
550    pub fn new(
551        tree: &'a StaticTopTree,
552        vertices: Vec<<C as Cluster>::Vertex>,
553        edges: Vec<<C as Cluster>::Edge>,
554    ) -> Self {
555        assert_eq!(vertices.len(), tree.vertices_size());
556        assert_eq!(edges.len(), tree.edges_size());
557
558        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
559        let path = tree.init_compress(
560            &mut data,
561            &vertices,
562            &edges,
563            tree.compress_roots[tree.root].expect("root compress tree must exist"),
564        );
565        let all_point = C::add_edge(&path);
566        Self {
567            tree,
568            vertices,
569            edges,
570            compressed: unsafe { assume_init_vec(data.compressed) },
571            raked: unsafe { assume_init_vec(data.raked) },
572            light_points: data.light_points,
573            all_point,
574        }
575    }
Source

pub fn dp<C>( &self, vertices: Vec<<C as Cluster>::Vertex>, edges: Vec<<C as Cluster>::Edge>, ) -> StaticTopTreeDp<'_, C>
where C: Cluster,

Examples found in repository?
crates/library_checker/src/tree/point_set_tree_path_composite_sum_fixed_root.rs (line 111)
103pub fn point_set_tree_path_composite_sum_fixed_root(reader: impl Read, writer: impl Write) {
104    prepare_io!(reader, writer);
105    sc!(n,
106        q,
107        value: [M; n],
108        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
109
110    let top_tree = graph.static_top_tree(0);
111    let mut dp = top_tree.dp::<Dp>(value, edges);
112
113    for _ in 0..q {
114        sc!(query: Query);
115        match query {
116            Query::SetVertex { v, x } => {
117                dp.set_vertex(v, x);
118                pp!(dp.fold_all().sum);
119            }
120            Query::SetEdge { e, a, b } => {
121                dp.set_edge(e, (a, b));
122                pp!(dp.fold_all().sum);
123            }
124        }
125    }
126}
More examples
Hide additional examples
crates/library_checker/src/tree/point_set_tree_path_composite_sum.rs (line 145)
137pub fn point_set_tree_path_composite_sum(reader: impl Read, writer: impl Write) {
138    prepare_io!(reader, writer);
139    sc!(n,
140        q,
141        value: [M; n],
142        (graph, edges): @TreeGraphScanner::<usize, (M, M)>::new(n));
143
144    let top_tree = graph.static_top_tree(0);
145    let mut dp = top_tree.dp::<Dp>(value, edges);
146
147    for _ in 0..q {
148        sc!(query: Query);
149        match query {
150            Query::SetVertex { v, x, r } => {
151                dp.set_vertex(v, x);
152                pp!(dp.fold_path(r).reverse.sum);
153            }
154            Query::SetEdge { e, a, b, r } => {
155                dp.set_edge(e, (a, b));
156                pp!(dp.fold_path(r).reverse.sum);
157            }
158        }
159    }
160}
Source

pub fn fold_all<C>( &self, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], ) -> <C as Cluster>::Point
where C: Cluster,

Source

fn build_compress( &mut self, vertex: usize, heavy_child: &[usize], mask: &[u64], ) -> Node

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 219)
156    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
157        let n = graph.vertices_size();
158        assert!(n > 0);
159        assert!(root < n);
160        assert_eq!(graph.edges_size() + 1, n);
161
162        let RootedInfo {
163            order,
164            children_start,
165            children,
166            edge_child,
167            parent_edge,
168        } = rooted_children(graph, root);
169        let mut this = Self {
170            root,
171            n,
172            edge_child,
173            parent_edge,
174            compressed: Vec::with_capacity(n.saturating_sub(1)),
175            raked: Vec::with_capacity(n.saturating_sub(1)),
176            vertex_links: vec![
177                VertexLinks {
178                    heavy_parent: usize::MAX,
179                    compress_parent: usize::MAX,
180                    rake_parent: usize::MAX,
181                };
182                n
183            ],
184            compress_roots: vec![None; n],
185            rake_roots: vec![None; n],
186        };
187
188        let mut heavy_child = vec![usize::MAX; n];
189        let mut mask = vec![1u64; n];
190        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());
191
192        for &u in order.iter().rev() {
193            let children = &children[children_start[u]..children_start[u + 1]];
194            let mut sum_rake = 0u64;
195            for &v in children {
196                sum_rake += bit_ceil(mask[v]) << 1;
197            }
198            mask[u] = bit_ceil(sum_rake);
199            for &v in children {
200                let child = bit_ceil(mask[v]) << 1;
201                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
202                let step = 1u64 << depth;
203                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
204                if cand <= mask[u] {
205                    mask[u] = cand;
206                    heavy_child[u] = v;
207                }
208            }
209
210            let mut has = 0u64;
211            let mut num_light = 0usize;
212            for &v in children {
213                if v == heavy_child[u] {
214                    continue;
215                }
216                num_light += 1;
217                let child = bit_ceil(mask[v]) << 1;
218                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
219                this.build_compress(v, &heavy_child, &mask);
220                buckets[depth].push(Node {
221                    depth,
222                    slot: Slot::RakeLeaf(v),
223                });
224                has |= 1u64 << depth;
225            }
226            if num_light == 0 {
227                continue;
228            }
229
230            while num_light > 1 {
231                let left = pop_bucket(&mut buckets, &mut has);
232                let right = pop_bucket(&mut buckets, &mut has);
233                let node = this.merge_rake(left, right);
234                let depth = node.depth;
235                buckets[depth].push(node);
236                has |= 1u64 << depth;
237                num_light -= 1;
238            }
239
240            let root = pop_bucket(&mut buckets, &mut has);
241            this.rake_roots[u] = Some(root.slot);
242            for &v0 in children {
243                if v0 == heavy_child[u] {
244                    continue;
245                }
246                let rake_parent = this.vertex_links[v0].rake_parent;
247                let mut v = v0;
248                while v != usize::MAX {
249                    this.vertex_links[v].heavy_parent = u;
250                    this.vertex_links[v].rake_parent = rake_parent;
251                    v = heavy_child[v];
252                }
253            }
254        }
255
256        this.build_compress(root, &heavy_child, &mask);
257        this
258    }
Source

fn merge_compress(&mut self, left: Node, right: Node) -> Node

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 314)
297    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
298        let start = vertex;
299        let mut stack = Vec::new();
300        while vertex != usize::MAX {
301            stack.push(Node {
302                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
303                slot: Slot::CompressLeaf(vertex),
304            });
305            loop {
306                let len = stack.len();
307                if len >= 3
308                    && (stack[len - 3].depth == stack[len - 2].depth
309                        || stack[len - 3].depth <= stack[len - 1].depth)
310                {
311                    let tail = stack.pop().unwrap();
312                    let right = stack.pop().unwrap();
313                    let left = stack.pop().unwrap();
314                    let node = self.merge_compress(left, right);
315                    stack.push(node);
316                    stack.push(tail);
317                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
318                    let right = stack.pop().unwrap();
319                    let left = stack.pop().unwrap();
320                    stack.push(self.merge_compress(left, right));
321                } else {
322                    break;
323                }
324            }
325            vertex = heavy_child[vertex];
326        }
327        while stack.len() > 1 {
328            let right = stack.pop().unwrap();
329            let left = stack.pop().unwrap();
330            stack.push(self.merge_compress(left, right));
331        }
332        let root = stack.pop().unwrap();
333        self.compress_roots[start] = Some(root.slot);
334        root
335    }
Source

fn merge_rake(&mut self, left: Node, right: Node) -> Node

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 233)
156    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
157        let n = graph.vertices_size();
158        assert!(n > 0);
159        assert!(root < n);
160        assert_eq!(graph.edges_size() + 1, n);
161
162        let RootedInfo {
163            order,
164            children_start,
165            children,
166            edge_child,
167            parent_edge,
168        } = rooted_children(graph, root);
169        let mut this = Self {
170            root,
171            n,
172            edge_child,
173            parent_edge,
174            compressed: Vec::with_capacity(n.saturating_sub(1)),
175            raked: Vec::with_capacity(n.saturating_sub(1)),
176            vertex_links: vec![
177                VertexLinks {
178                    heavy_parent: usize::MAX,
179                    compress_parent: usize::MAX,
180                    rake_parent: usize::MAX,
181                };
182                n
183            ],
184            compress_roots: vec![None; n],
185            rake_roots: vec![None; n],
186        };
187
188        let mut heavy_child = vec![usize::MAX; n];
189        let mut mask = vec![1u64; n];
190        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());
191
192        for &u in order.iter().rev() {
193            let children = &children[children_start[u]..children_start[u + 1]];
194            let mut sum_rake = 0u64;
195            for &v in children {
196                sum_rake += bit_ceil(mask[v]) << 1;
197            }
198            mask[u] = bit_ceil(sum_rake);
199            for &v in children {
200                let child = bit_ceil(mask[v]) << 1;
201                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
202                let step = 1u64 << depth;
203                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
204                if cand <= mask[u] {
205                    mask[u] = cand;
206                    heavy_child[u] = v;
207                }
208            }
209
210            let mut has = 0u64;
211            let mut num_light = 0usize;
212            for &v in children {
213                if v == heavy_child[u] {
214                    continue;
215                }
216                num_light += 1;
217                let child = bit_ceil(mask[v]) << 1;
218                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
219                this.build_compress(v, &heavy_child, &mask);
220                buckets[depth].push(Node {
221                    depth,
222                    slot: Slot::RakeLeaf(v),
223                });
224                has |= 1u64 << depth;
225            }
226            if num_light == 0 {
227                continue;
228            }
229
230            while num_light > 1 {
231                let left = pop_bucket(&mut buckets, &mut has);
232                let right = pop_bucket(&mut buckets, &mut has);
233                let node = this.merge_rake(left, right);
234                let depth = node.depth;
235                buckets[depth].push(node);
236                has |= 1u64 << depth;
237                num_light -= 1;
238            }
239
240            let root = pop_bucket(&mut buckets, &mut has);
241            this.rake_roots[u] = Some(root.slot);
242            for &v0 in children {
243                if v0 == heavy_child[u] {
244                    continue;
245                }
246                let rake_parent = this.vertex_links[v0].rake_parent;
247                let mut v = v0;
248                while v != usize::MAX {
249                    this.vertex_links[v].heavy_parent = u;
250                    this.vertex_links[v].rake_parent = rake_parent;
251                    v = heavy_child[v];
252                }
253            }
254        }
255
256        this.build_compress(root, &heavy_child, &mask);
257        this
258    }
Source

fn set_parent(&mut self, slot: Slot, parent: usize)

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 339)
337    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
338        let id = self.compressed.len();
339        self.set_parent(left.slot, id << 1);
340        self.set_parent(right.slot, id << 1 | 1);
341        self.compressed.push(InnerNode {
342            left: left.slot,
343            right: right.slot,
344            parent: usize::MAX,
345        });
346        Node {
347            depth: left.depth.max(right.depth) + 1,
348            slot: Slot::CompressInner(id),
349        }
350    }
351
352    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
353        let id = self.raked.len();
354        self.set_parent(left.slot, id << 1);
355        self.set_parent(right.slot, id << 1 | 1);
356        self.raked.push(InnerNode {
357            left: left.slot,
358            right: right.slot,
359            parent: usize::MAX,
360        });
361        Node {
362            depth: left.depth.max(right.depth) + 1,
363            slot: Slot::RakeInner(id),
364        }
365    }
Source

fn init_compress<C>( &self, data: &mut StaticTopTreeDataBuilder<C>, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], slot: Slot, ) -> <C as Cluster>::Path
where C: Cluster,

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 397)
376    fn init_compress<C>(
377        &self,
378        data: &mut StaticTopTreeDataBuilder<C>,
379        vertices: &[<C as Cluster>::Vertex],
380        edges: &[<C as Cluster>::Edge],
381        slot: Slot,
382    ) -> <C as Cluster>::Path
383    where
384        C: Cluster,
385    {
386        match slot {
387            Slot::CompressLeaf(vertex) => {
388                let point = self.init_point(data, vertices, edges, vertex);
389                C::add_vertex(
390                    &point,
391                    &vertices[vertex],
392                    self.parent_edge_ref(edges, vertex),
393                )
394            }
395            Slot::CompressInner(id) => {
396                let node = &self.compressed[id];
397                let left = self.init_compress(data, vertices, edges, node.left);
398                let right = self.init_compress(data, vertices, edges, node.right);
399                data.compressed[id].write(InnerValue {
400                    parent: node.parent,
401                    left: left.clone(),
402                    right: right.clone(),
403                });
404                C::compress(&left, &right)
405            }
406            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
407        }
408    }
409
410    fn fold_compress<C>(
411        &self,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Path
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::CompressLeaf(vertex) => {
421                let point = self.fold_point::<C>(vertices, edges, vertex);
422                C::add_vertex(
423                    &point,
424                    &vertices[vertex],
425                    self.parent_edge_ref(edges, vertex),
426                )
427            }
428            Slot::CompressInner(id) => {
429                let node = &self.compressed[id];
430                let left = self.fold_compress::<C>(vertices, edges, node.left);
431                let right = self.fold_compress::<C>(vertices, edges, node.right);
432                C::compress(&left, &right)
433            }
434            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
435        }
436    }
437
438    fn init_point<C>(
439        &self,
440        data: &mut StaticTopTreeDataBuilder<C>,
441        vertices: &[<C as Cluster>::Vertex],
442        edges: &[<C as Cluster>::Edge],
443        vertex: usize,
444    ) -> <C as Cluster>::Point
445    where
446        C: Cluster,
447    {
448        let point = if let Some(slot) = self.rake_roots[vertex] {
449            self.init_rake(data, vertices, edges, slot)
450        } else {
451            C::unit_point()
452        };
453        data.light_points[vertex] = point.clone();
454        point
455    }
456
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
507
508    fn fold_rake<C>(
509        &self,
510        vertices: &[<C as Cluster>::Vertex],
511        edges: &[<C as Cluster>::Edge],
512        slot: Slot,
513    ) -> <C as Cluster>::Point
514    where
515        C: Cluster,
516    {
517        match slot {
518            Slot::RakeLeaf(vertex) => {
519                let path = self.fold_compress::<C>(
520                    vertices,
521                    edges,
522                    self.compress_roots[vertex].expect("light child path must exist"),
523                );
524                C::add_edge(&path)
525            }
526            Slot::RakeInner(id) => {
527                let node = &self.raked[id];
528                let left = self.fold_rake::<C>(vertices, edges, node.left);
529                let right = self.fold_rake::<C>(vertices, edges, node.right);
530                C::rake(&left, &right)
531            }
532            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
533        }
534    }
535
536    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
537        let edge = self.parent_edge[vertex];
538        if edge == usize::MAX {
539            None
540        } else {
541            Some(&edges[edge])
542        }
543    }
544}
545
546impl<'a, C> StaticTopTreeDp<'a, C>
547where
548    C: Cluster,
549{
550    pub fn new(
551        tree: &'a StaticTopTree,
552        vertices: Vec<<C as Cluster>::Vertex>,
553        edges: Vec<<C as Cluster>::Edge>,
554    ) -> Self {
555        assert_eq!(vertices.len(), tree.vertices_size());
556        assert_eq!(edges.len(), tree.edges_size());
557
558        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
559        let path = tree.init_compress(
560            &mut data,
561            &vertices,
562            &edges,
563            tree.compress_roots[tree.root].expect("root compress tree must exist"),
564        );
565        let all_point = C::add_edge(&path);
566        Self {
567            tree,
568            vertices,
569            edges,
570            compressed: unsafe { assume_init_vec(data.compressed) },
571            raked: unsafe { assume_init_vec(data.raked) },
572            light_points: data.light_points,
573            all_point,
574        }
575    }
Source

fn fold_compress<C>( &self, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], slot: Slot, ) -> <C as Cluster>::Path
where C: Cluster,

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (lines 289-293)
279    pub fn fold_all<C>(
280        &self,
281        vertices: &[<C as Cluster>::Vertex],
282        edges: &[<C as Cluster>::Edge],
283    ) -> <C as Cluster>::Point
284    where
285        C: Cluster,
286    {
287        assert_eq!(vertices.len(), self.vertices_size());
288        assert_eq!(edges.len(), self.edges_size());
289        let path = self.fold_compress::<C>(
290            vertices,
291            edges,
292            self.compress_roots[self.root].expect("root compress tree must exist"),
293        );
294        C::add_edge(&path)
295    }
296
297    fn build_compress(&mut self, mut vertex: usize, heavy_child: &[usize], mask: &[u64]) -> Node {
298        let start = vertex;
299        let mut stack = Vec::new();
300        while vertex != usize::MAX {
301            stack.push(Node {
302                depth: bit_ceil(mask[vertex]).trailing_zeros() as usize,
303                slot: Slot::CompressLeaf(vertex),
304            });
305            loop {
306                let len = stack.len();
307                if len >= 3
308                    && (stack[len - 3].depth == stack[len - 2].depth
309                        || stack[len - 3].depth <= stack[len - 1].depth)
310                {
311                    let tail = stack.pop().unwrap();
312                    let right = stack.pop().unwrap();
313                    let left = stack.pop().unwrap();
314                    let node = self.merge_compress(left, right);
315                    stack.push(node);
316                    stack.push(tail);
317                } else if len >= 2 && stack[len - 2].depth <= stack[len - 1].depth {
318                    let right = stack.pop().unwrap();
319                    let left = stack.pop().unwrap();
320                    stack.push(self.merge_compress(left, right));
321                } else {
322                    break;
323                }
324            }
325            vertex = heavy_child[vertex];
326        }
327        while stack.len() > 1 {
328            let right = stack.pop().unwrap();
329            let left = stack.pop().unwrap();
330            stack.push(self.merge_compress(left, right));
331        }
332        let root = stack.pop().unwrap();
333        self.compress_roots[start] = Some(root.slot);
334        root
335    }
336
337    fn merge_compress(&mut self, left: Node, right: Node) -> Node {
338        let id = self.compressed.len();
339        self.set_parent(left.slot, id << 1);
340        self.set_parent(right.slot, id << 1 | 1);
341        self.compressed.push(InnerNode {
342            left: left.slot,
343            right: right.slot,
344            parent: usize::MAX,
345        });
346        Node {
347            depth: left.depth.max(right.depth) + 1,
348            slot: Slot::CompressInner(id),
349        }
350    }
351
352    fn merge_rake(&mut self, left: Node, right: Node) -> Node {
353        let id = self.raked.len();
354        self.set_parent(left.slot, id << 1);
355        self.set_parent(right.slot, id << 1 | 1);
356        self.raked.push(InnerNode {
357            left: left.slot,
358            right: right.slot,
359            parent: usize::MAX,
360        });
361        Node {
362            depth: left.depth.max(right.depth) + 1,
363            slot: Slot::RakeInner(id),
364        }
365    }
366
367    fn set_parent(&mut self, slot: Slot, parent: usize) {
368        match slot {
369            Slot::CompressLeaf(v) => self.vertex_links[v].compress_parent = parent,
370            Slot::CompressInner(i) => self.compressed[i].parent = parent,
371            Slot::RakeLeaf(v) => self.vertex_links[v].rake_parent = parent,
372            Slot::RakeInner(i) => self.raked[i].parent = parent,
373        }
374    }
375
376    fn init_compress<C>(
377        &self,
378        data: &mut StaticTopTreeDataBuilder<C>,
379        vertices: &[<C as Cluster>::Vertex],
380        edges: &[<C as Cluster>::Edge],
381        slot: Slot,
382    ) -> <C as Cluster>::Path
383    where
384        C: Cluster,
385    {
386        match slot {
387            Slot::CompressLeaf(vertex) => {
388                let point = self.init_point(data, vertices, edges, vertex);
389                C::add_vertex(
390                    &point,
391                    &vertices[vertex],
392                    self.parent_edge_ref(edges, vertex),
393                )
394            }
395            Slot::CompressInner(id) => {
396                let node = &self.compressed[id];
397                let left = self.init_compress(data, vertices, edges, node.left);
398                let right = self.init_compress(data, vertices, edges, node.right);
399                data.compressed[id].write(InnerValue {
400                    parent: node.parent,
401                    left: left.clone(),
402                    right: right.clone(),
403                });
404                C::compress(&left, &right)
405            }
406            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
407        }
408    }
409
410    fn fold_compress<C>(
411        &self,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Path
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::CompressLeaf(vertex) => {
421                let point = self.fold_point::<C>(vertices, edges, vertex);
422                C::add_vertex(
423                    &point,
424                    &vertices[vertex],
425                    self.parent_edge_ref(edges, vertex),
426                )
427            }
428            Slot::CompressInner(id) => {
429                let node = &self.compressed[id];
430                let left = self.fold_compress::<C>(vertices, edges, node.left);
431                let right = self.fold_compress::<C>(vertices, edges, node.right);
432                C::compress(&left, &right)
433            }
434            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
435        }
436    }
437
438    fn init_point<C>(
439        &self,
440        data: &mut StaticTopTreeDataBuilder<C>,
441        vertices: &[<C as Cluster>::Vertex],
442        edges: &[<C as Cluster>::Edge],
443        vertex: usize,
444    ) -> <C as Cluster>::Point
445    where
446        C: Cluster,
447    {
448        let point = if let Some(slot) = self.rake_roots[vertex] {
449            self.init_rake(data, vertices, edges, slot)
450        } else {
451            C::unit_point()
452        };
453        data.light_points[vertex] = point.clone();
454        point
455    }
456
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
507
508    fn fold_rake<C>(
509        &self,
510        vertices: &[<C as Cluster>::Vertex],
511        edges: &[<C as Cluster>::Edge],
512        slot: Slot,
513    ) -> <C as Cluster>::Point
514    where
515        C: Cluster,
516    {
517        match slot {
518            Slot::RakeLeaf(vertex) => {
519                let path = self.fold_compress::<C>(
520                    vertices,
521                    edges,
522                    self.compress_roots[vertex].expect("light child path must exist"),
523                );
524                C::add_edge(&path)
525            }
526            Slot::RakeInner(id) => {
527                let node = &self.raked[id];
528                let left = self.fold_rake::<C>(vertices, edges, node.left);
529                let right = self.fold_rake::<C>(vertices, edges, node.right);
530                C::rake(&left, &right)
531            }
532            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
533        }
534    }
Source

fn init_point<C>( &self, data: &mut StaticTopTreeDataBuilder<C>, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], vertex: usize, ) -> <C as Cluster>::Point
where C: Cluster,

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 388)
376    fn init_compress<C>(
377        &self,
378        data: &mut StaticTopTreeDataBuilder<C>,
379        vertices: &[<C as Cluster>::Vertex],
380        edges: &[<C as Cluster>::Edge],
381        slot: Slot,
382    ) -> <C as Cluster>::Path
383    where
384        C: Cluster,
385    {
386        match slot {
387            Slot::CompressLeaf(vertex) => {
388                let point = self.init_point(data, vertices, edges, vertex);
389                C::add_vertex(
390                    &point,
391                    &vertices[vertex],
392                    self.parent_edge_ref(edges, vertex),
393                )
394            }
395            Slot::CompressInner(id) => {
396                let node = &self.compressed[id];
397                let left = self.init_compress(data, vertices, edges, node.left);
398                let right = self.init_compress(data, vertices, edges, node.right);
399                data.compressed[id].write(InnerValue {
400                    parent: node.parent,
401                    left: left.clone(),
402                    right: right.clone(),
403                });
404                C::compress(&left, &right)
405            }
406            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
407        }
408    }
Source

fn fold_point<C>( &self, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], vertex: usize, ) -> <C as Cluster>::Point
where C: Cluster,

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 421)
410    fn fold_compress<C>(
411        &self,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Path
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::CompressLeaf(vertex) => {
421                let point = self.fold_point::<C>(vertices, edges, vertex);
422                C::add_vertex(
423                    &point,
424                    &vertices[vertex],
425                    self.parent_edge_ref(edges, vertex),
426                )
427            }
428            Slot::CompressInner(id) => {
429                let node = &self.compressed[id];
430                let left = self.fold_compress::<C>(vertices, edges, node.left);
431                let right = self.fold_compress::<C>(vertices, edges, node.right);
432                C::compress(&left, &right)
433            }
434            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
435        }
436    }
Source

fn init_rake<C>( &self, data: &mut StaticTopTreeDataBuilder<C>, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], slot: Slot, ) -> <C as Cluster>::Point
where C: Cluster,

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 449)
438    fn init_point<C>(
439        &self,
440        data: &mut StaticTopTreeDataBuilder<C>,
441        vertices: &[<C as Cluster>::Vertex],
442        edges: &[<C as Cluster>::Edge],
443        vertex: usize,
444    ) -> <C as Cluster>::Point
445    where
446        C: Cluster,
447    {
448        let point = if let Some(slot) = self.rake_roots[vertex] {
449            self.init_rake(data, vertices, edges, slot)
450        } else {
451            C::unit_point()
452        };
453        data.light_points[vertex] = point.clone();
454        point
455    }
456
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
Source

fn fold_rake<C>( &self, vertices: &[<C as Cluster>::Vertex], edges: &[<C as Cluster>::Edge], slot: Slot, ) -> <C as Cluster>::Point
where C: Cluster,

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 467)
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
507
508    fn fold_rake<C>(
509        &self,
510        vertices: &[<C as Cluster>::Vertex],
511        edges: &[<C as Cluster>::Edge],
512        slot: Slot,
513    ) -> <C as Cluster>::Point
514    where
515        C: Cluster,
516    {
517        match slot {
518            Slot::RakeLeaf(vertex) => {
519                let path = self.fold_compress::<C>(
520                    vertices,
521                    edges,
522                    self.compress_roots[vertex].expect("light child path must exist"),
523                );
524                C::add_edge(&path)
525            }
526            Slot::RakeInner(id) => {
527                let node = &self.raked[id];
528                let left = self.fold_rake::<C>(vertices, edges, node.left);
529                let right = self.fold_rake::<C>(vertices, edges, node.right);
530                C::rake(&left, &right)
531            }
532            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
533        }
534    }
Source

fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T>

Examples found in repository?
crates/competitive/src/tree/static_top_tree.rs (line 392)
376    fn init_compress<C>(
377        &self,
378        data: &mut StaticTopTreeDataBuilder<C>,
379        vertices: &[<C as Cluster>::Vertex],
380        edges: &[<C as Cluster>::Edge],
381        slot: Slot,
382    ) -> <C as Cluster>::Path
383    where
384        C: Cluster,
385    {
386        match slot {
387            Slot::CompressLeaf(vertex) => {
388                let point = self.init_point(data, vertices, edges, vertex);
389                C::add_vertex(
390                    &point,
391                    &vertices[vertex],
392                    self.parent_edge_ref(edges, vertex),
393                )
394            }
395            Slot::CompressInner(id) => {
396                let node = &self.compressed[id];
397                let left = self.init_compress(data, vertices, edges, node.left);
398                let right = self.init_compress(data, vertices, edges, node.right);
399                data.compressed[id].write(InnerValue {
400                    parent: node.parent,
401                    left: left.clone(),
402                    right: right.clone(),
403                });
404                C::compress(&left, &right)
405            }
406            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
407        }
408    }
409
410    fn fold_compress<C>(
411        &self,
412        vertices: &[<C as Cluster>::Vertex],
413        edges: &[<C as Cluster>::Edge],
414        slot: Slot,
415    ) -> <C as Cluster>::Path
416    where
417        C: Cluster,
418    {
419        match slot {
420            Slot::CompressLeaf(vertex) => {
421                let point = self.fold_point::<C>(vertices, edges, vertex);
422                C::add_vertex(
423                    &point,
424                    &vertices[vertex],
425                    self.parent_edge_ref(edges, vertex),
426                )
427            }
428            Slot::CompressInner(id) => {
429                let node = &self.compressed[id];
430                let left = self.fold_compress::<C>(vertices, edges, node.left);
431                let right = self.fold_compress::<C>(vertices, edges, node.right);
432                C::compress(&left, &right)
433            }
434            Slot::RakeLeaf(_) | Slot::RakeInner(_) => unreachable!(),
435        }
436    }
437
438    fn init_point<C>(
439        &self,
440        data: &mut StaticTopTreeDataBuilder<C>,
441        vertices: &[<C as Cluster>::Vertex],
442        edges: &[<C as Cluster>::Edge],
443        vertex: usize,
444    ) -> <C as Cluster>::Point
445    where
446        C: Cluster,
447    {
448        let point = if let Some(slot) = self.rake_roots[vertex] {
449            self.init_rake(data, vertices, edges, slot)
450        } else {
451            C::unit_point()
452        };
453        data.light_points[vertex] = point.clone();
454        point
455    }
456
457    fn fold_point<C>(
458        &self,
459        vertices: &[<C as Cluster>::Vertex],
460        edges: &[<C as Cluster>::Edge],
461        vertex: usize,
462    ) -> <C as Cluster>::Point
463    where
464        C: Cluster,
465    {
466        if let Some(slot) = self.rake_roots[vertex] {
467            self.fold_rake::<C>(vertices, edges, slot)
468        } else {
469            C::unit_point()
470        }
471    }
472
473    fn init_rake<C>(
474        &self,
475        data: &mut StaticTopTreeDataBuilder<C>,
476        vertices: &[<C as Cluster>::Vertex],
477        edges: &[<C as Cluster>::Edge],
478        slot: Slot,
479    ) -> <C as Cluster>::Point
480    where
481        C: Cluster,
482    {
483        match slot {
484            Slot::RakeLeaf(vertex) => {
485                let path = self.init_compress(
486                    data,
487                    vertices,
488                    edges,
489                    self.compress_roots[vertex].expect("light child path must exist"),
490                );
491                C::add_edge(&path)
492            }
493            Slot::RakeInner(id) => {
494                let node = &self.raked[id];
495                let left = self.init_rake(data, vertices, edges, node.left);
496                let right = self.init_rake(data, vertices, edges, node.right);
497                data.raked[id].write(InnerValue {
498                    parent: node.parent,
499                    left: left.clone(),
500                    right: right.clone(),
501                });
502                C::rake(&left, &right)
503            }
504            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
505        }
506    }
507
508    fn fold_rake<C>(
509        &self,
510        vertices: &[<C as Cluster>::Vertex],
511        edges: &[<C as Cluster>::Edge],
512        slot: Slot,
513    ) -> <C as Cluster>::Point
514    where
515        C: Cluster,
516    {
517        match slot {
518            Slot::RakeLeaf(vertex) => {
519                let path = self.fold_compress::<C>(
520                    vertices,
521                    edges,
522                    self.compress_roots[vertex].expect("light child path must exist"),
523                );
524                C::add_edge(&path)
525            }
526            Slot::RakeInner(id) => {
527                let node = &self.raked[id];
528                let left = self.fold_rake::<C>(vertices, edges, node.left);
529                let right = self.fold_rake::<C>(vertices, edges, node.right);
530                C::rake(&left, &right)
531            }
532            Slot::CompressLeaf(_) | Slot::CompressInner(_) => unreachable!(),
533        }
534    }
535
536    fn parent_edge_ref<'a, T>(&self, edges: &'a [T], vertex: usize) -> Option<&'a T> {
537        let edge = self.parent_edge[vertex];
538        if edge == usize::MAX {
539            None
540        } else {
541            Some(&edges[edge])
542        }
543    }
544}
545
546impl<'a, C> StaticTopTreeDp<'a, C>
547where
548    C: Cluster,
549{
550    pub fn new(
551        tree: &'a StaticTopTree,
552        vertices: Vec<<C as Cluster>::Vertex>,
553        edges: Vec<<C as Cluster>::Edge>,
554    ) -> Self {
555        assert_eq!(vertices.len(), tree.vertices_size());
556        assert_eq!(edges.len(), tree.edges_size());
557
558        let mut data: StaticTopTreeDataBuilder<C> = StaticTopTreeDataBuilder::new(tree);
559        let path = tree.init_compress(
560            &mut data,
561            &vertices,
562            &edges,
563            tree.compress_roots[tree.root].expect("root compress tree must exist"),
564        );
565        let all_point = C::add_edge(&path);
566        Self {
567            tree,
568            vertices,
569            edges,
570            compressed: unsafe { assume_init_vec(data.compressed) },
571            raked: unsafe { assume_init_vec(data.raked) },
572            light_points: data.light_points,
573            all_point,
574        }
575    }
576
577    pub fn get_vertex(&self, vertex: usize) -> &<C as Cluster>::Vertex {
578        &self.vertices[vertex]
579    }
580
581    pub fn apply_vertex<F>(&mut self, vertex: usize, f: F)
582    where
583        F: FnOnce(&mut <C as Cluster>::Vertex),
584    {
585        assert!(vertex < self.vertices.len());
586        f(&mut self.vertices[vertex]);
587        self.update_from_vertex(vertex);
588    }
589
590    pub fn set_vertex(&mut self, vertex: usize, value: <C as Cluster>::Vertex) {
591        self.apply_vertex(vertex, |x| *x = value);
592    }
593
594    pub fn get_edge(&self, edge: usize) -> &<C as Cluster>::Edge {
595        &self.edges[edge]
596    }
597
598    pub fn apply_edge<F>(&mut self, edge: usize, f: F)
599    where
600        F: FnOnce(&mut <C as Cluster>::Edge),
601    {
602        assert!(edge < self.edges.len());
603        f(&mut self.edges[edge]);
604        self.update_from_vertex(self.tree.edge_child[edge]);
605    }
606
607    pub fn set_edge(&mut self, edge: usize, value: <C as Cluster>::Edge) {
608        self.apply_edge(edge, |x| *x = value);
609    }
610
611    pub fn fold_all(&self) -> &<C as Cluster>::Point {
612        &self.all_point
613    }
614
615    #[inline(always)]
616    pub fn fold_path(&self, mut vertex: usize) -> <C as Cluster>::Path {
617        assert!(vertex < self.tree.n);
618        let mut path = C::unit_path();
619        let mut point = self.light_points[vertex].clone();
620        loop {
621            let links = self.tree.vertex_links[vertex];
622            let mut left = C::unit_path();
623            let mut right = C::unit_path();
624            let mut compress_parent = links.compress_parent;
625            while compress_parent != usize::MAX {
626                let inner = &self.compressed[compress_parent / 2];
627                if compress_parent & 1 == 0 {
628                    right = C::compress(&right, &inner.right);
629                } else {
630                    left = C::compress(&inner.left, &left);
631                }
632                compress_parent = inner.parent;
633            }
634            let right_point = C::add_edge(&right);
635            point = C::rake(&point, &right_point);
636            let mid = C::add_vertex(
637                &point,
638                &self.vertices[vertex],
639                self.tree.parent_edge_ref(&self.edges, vertex),
640            );
641            let mid = C::compress(&mid, &path);
642            path = C::compress(&left, &mid);
643            if links.heavy_parent == usize::MAX {
644                return path;
645            }
646
647            point = C::unit_point();
648            let mut rake_parent = links.rake_parent;
649            while rake_parent != usize::MAX {
650                let inner = &self.raked[rake_parent / 2];
651                if rake_parent & 1 == 0 {
652                    point = C::rake(&point, &inner.right);
653                } else {
654                    point = C::rake(&inner.left, &point);
655                }
656                rake_parent = inner.parent;
657            }
658            vertex = links.heavy_parent;
659        }
660    }
661
662    fn update_from_vertex(&mut self, mut vertex: usize) {
663        assert!(vertex < self.tree.n);
664        while vertex != usize::MAX {
665            let links = self.tree.vertex_links[vertex];
666            let base = C::add_vertex(
667                &self.light_points[vertex],
668                &self.vertices[vertex],
669                self.tree.parent_edge_ref(&self.edges, vertex),
670            );
671            let path = self.update_compress(links.compress_parent, base);
672            let point = C::add_edge(&path);
673            let point = self.update_rake(links.rake_parent, point);
674            if links.heavy_parent == usize::MAX {
675                self.all_point = point;
676            } else {
677                self.light_points[links.heavy_parent] = point;
678            }
679            vertex = links.heavy_parent;
680        }
681    }

Trait Implementations§

Source§

impl Clone for StaticTopTree

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

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.