Function rooted_children 

fn rooted_children(graph: &UndirectedSparseGraph, root: usize) -> RootedInfo

Examples found in repository

crates/competitive/src/tree/static_top_tree.rs (line 168)

    pub fn new(root: usize, graph: &UndirectedSparseGraph) -> Self {
        let n = graph.vertices_size();
        assert!(n > 0);
        assert!(root < n);
        assert_eq!(graph.edges_size() + 1, n);

        let RootedInfo {
            order,
            children_start,
            children,
            edge_child,
            parent_edge,
        } = rooted_children(graph, root);
        let mut this = Self {
            root,
            n,
            edge_child,
            parent_edge,
            compressed: Vec::with_capacity(n.saturating_sub(1)),
            raked: Vec::with_capacity(n.saturating_sub(1)),
            vertex_links: vec![
                VertexLinks {
                    heavy_parent: usize::MAX,
                    compress_parent: usize::MAX,
                    rake_parent: usize::MAX,
                };
                n
            ],
            compress_roots: vec![None; n],
            rake_roots: vec![None; n],
        };

        let mut heavy_child = vec![usize::MAX; n];
        let mut mask = vec![1u64; n];
        let mut buckets: [Vec<Node>; 64] = std::array::from_fn(|_| Vec::new());

        for &u in order.iter().rev() {
            let children = &children[children_start[u]..children_start[u + 1]];
            let mut sum_rake = 0u64;
            for &v in children {
                sum_rake += bit_ceil(mask[v]) << 1;
            }
            mask[u] = bit_ceil(sum_rake);
            for &v in children {
                let child = bit_ceil(mask[v]) << 1;
                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
                let step = 1u64 << depth;
                let cand = ((mask[v] + step - 1) >> depth << depth) + step;
                if cand <= mask[u] {
                    mask[u] = cand;
                    heavy_child[u] = v;
                }
            }

            let mut has = 0u64;
            let mut num_light = 0usize;
            for &v in children {
                if v == heavy_child[u] {
                    continue;
                }
                num_light += 1;
                let child = bit_ceil(mask[v]) << 1;
                let depth = bit_ceil(sum_rake - child).trailing_zeros() as usize;
                this.build_compress(v, &heavy_child, &mask);
                buckets[depth].push(Node {
                    depth,
                    slot: Slot::RakeLeaf(v),
                });
                has |= 1u64 << depth;
            }
            if num_light == 0 {
                continue;
            }

            while num_light > 1 {
                let left = pop_bucket(&mut buckets, &mut has);
                let right = pop_bucket(&mut buckets, &mut has);
                let node = this.merge_rake(left, right);
                let depth = node.depth;
                buckets[depth].push(node);
                has |= 1u64 << depth;
                num_light -= 1;
            }

            let root = pop_bucket(&mut buckets, &mut has);
            this.rake_roots[u] = Some(root.slot);
            for &v0 in children {
                if v0 == heavy_child[u] {
                    continue;
                }
                let rake_parent = this.vertex_links[v0].rake_parent;
                let mut v = v0;
                while v != usize::MAX {
                    this.vertex_links[v].heavy_parent = u;
                    this.vertex_links[v].rake_parent = rake_parent;
                    v = heavy_child[v];
                }
            }
        }

        this.build_compress(root, &heavy_child, &mask);
        this
    }