Crate centroid_decomposition 

Centroid Decomposition of a tree.

Centroid decomposition recursively splits a tree at its centroid — the vertex whose removal leaves components of size at most n/2 — and repeats on each component. The resulting recursion tree has height O(log n), and any two original vertices share an ancestor in the decomposition at depth at most O(log n).

This is the foundation for “small-to-large” tricks on trees, for answering distance queries offline (count paths of length ≤ k), and for many divide-and-conquer-on-tree problems.

This crate exposes build_centroid_tree, which returns the centroid tree: for each vertex, the centroid chosen at the next level up (its “centroid parent”) and the depth of the vertex in the centroid tree.

Example

use centroid_decomposition::build_centroid_tree;

// Path 0 -- 1 -- 2 -- 3 -- 4
let adj = vec![
    vec![1],
    vec![0, 2],
    vec![1, 3],
    vec![2, 4],
    vec![3],
];
let (parent, depth) = build_centroid_tree(&adj);
// Centroid of a 5-path is the middle vertex (2).
assert_eq!(parent[2], None);

Functions

build_centroid_tree

Build the centroid decomposition of the tree adj.