Centroid Decomposition

Centroid Decomposition is a technique for dividing a tree into smaller subtrees by repeatedly removing centroids. It is useful for solving various problems on trees using divide-and-conquer.

Centroid Definition

A centroid of a tree is a node such that, if removed, all resulting subtrees have at most $n/2$ nodes (where $n$ is the size of the original tree).

• Every tree has either one or two centroids.
• Centroid decomposition recursively removes centroids to break the tree into smaller parts.

Finding the Centroid

To find the centroid:

1. Compute the size of each subtree using DFS.
2. For each node, check if the largest resulting subtree (after removing the node) has at most $n/2$ nodes.

Implementation

vector<vector<int>> adj;
vector<int> subtreeSize;
int n;

void dfs(int u, int p) {
    subtreeSize[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            subtreeSize[u] += subtreeSize[v];
        }
    }
}

int findCentroid(int u, int p, int total) {
    for (int v : adj[u]) {
        if (v != p && subtreeSize[v] > total / 2) {
            return findCentroid(v, u, total);
        }
    }
    return u;
}

Centroid Decomposition Algorithm

The decomposition is performed recursively:

1. Find the centroid of the current tree.
2. Remove the centroid and recursively decompose each subtree.

Example Skeleton

void centroidDecompose(int u, int p) {
    dfs(u, -1);
    int c = findCentroid(u, -1, subtreeSize[u]);
    // Process centroid c here
    for (int v : adj[c]) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), c));
        centroidDecompose(v, c);
    }
}

Applications

• Solving path/counting problems efficiently on trees
• Dynamic programming on trees
• Range queries and updates on trees

Centroid decomposition is a powerful tool for advanced tree algorithms.