When dealing with problems that involve paths in a tree (like "how many paths have a length exactly $K$?"), a simple DFS might take $O(N^2)$. Centroid Decomposition is a divide-and-conquer technique that reduces this complexity to $O(N \log N)$.
The Core Concept: The Centroid
A centroid of a tree is a node whose removal splits the tree into subtrees, each having at most $N/2$ nodes. Every tree has at least one (and at most two) centroids.
- Finding the Centroid: Use DFS to calculate subtree sizes and identify the node that satisfies the centroid property.
- Recursive Decomposition: Once the centroid is found, "remove" it and recursively decompose the resulting subtrees.
- Centroid Tree: This process creates a new tree structure (the Centroid Tree) with a height of at most $O(\log N)$.
Centroid Decomposition Implementation in Java
import java.util.*;
public class CentroidDecomposition {
private int n;
private List<Integer>[] adj;
private boolean[] removed;
private int[] subtreeSize;
public CentroidDecomposition(int n, List<Integer>[] adj) {
this.n = n;
this.adj = adj;
this.removed = new boolean[n];
this.subtreeSize = new int[n];
decompose(0, -1);
}
private void computeSubtreeSize(int u, int p) {
subtreeSize[u] = 1;
for (int v : adj[u]) {
if (v != p && !removed[v]) {
computeSubtreeSize(v, u);
subtreeSize[u] += subtreeSize[v];
}
}
}
private int findCentroid(int u, int p, int totalSize) {
for (int v : adj[u]) {
if (v != p && !removed[v] && subtreeSize[v] > totalSize / 2) {
return findCentroid(v, u, totalSize);
}
}
return u;
}
private void decompose(int u, int p) {
computeSubtreeSize(u, -1);
int centroid = findCentroid(u, -1, subtreeSize[u]);
// Process paths passing through the centroid
processCentroid(centroid);
removed[centroid] = true;
for (int v : adj[centroid]) {
if (!removed[v]) {
decompose(v, centroid);
}
}
}
private void processCentroid(int centroid) {
// Logic to solve the specific path problem
// e.g., counting paths of length K using a frequency map
}
}
Why use Centroid Decomposition?
| Feature | Centroid Decomposition | Heavy-Light Decomposition |
|---|---|---|
| Primary Use | Path counting/properties | Path updates/queries |
| Complexity | $O(N \log N)$ | $O(N \log^2 N)$ |
| Structure | Recursive Divide & Conquer | Path-based Partitioning |
| Best For | Global path problems | Dynamic path queries |
Real-World Applications
- Network Analysis: Analyzing properties of all possible communication paths in a hierarchical network.
- Computational Biology: Studying structural properties of tree-like molecular structures.
- Competitive Programming: Solving advanced tree problems involving path lengths, weights, or specific node properties.
Summary
Centroid Decomposition is a brilliant application of the divide-and-conquer paradigm to tree structures. By ensuring that each step reduces the problem size by at least half, it provides a robust framework for solving complex path problems that would otherwise be computationally expensive. While the implementation requires careful handling of subtree sizes and recursion, the efficiency it brings to tree algorithms is unparalleled.
