Centroid Decomposition

Centroid decomposition builds a balanced hierarchy by repeatedly removing a centroid. A centroid is a vertex whose removal leaves no component larger than half the current component. This differs from an ordinary rooting and from a tree center, which minimizes maximum distance. The hierarchy is useful when a path problem splits into paths through one separator and paths entirely inside one remaining component. We will build the hierarchy and explain how it supports more advanced queries.

Prerequisites: Subtree sizes, centroids, tree distances, and divide-and-conquer.

Build the idea

1. 1. Find a centroid of one component. Ignore already removed vertices. Root the current component temporarily at any active vertex and compute local subtree sizes. After removing candidate v, the pieces have sizes size[child] for local children, and total−size[v] for the parent side. The largest must be at most total/2. The parent-side term matters: a vertex with small child subtrees can leave a huge component above it. These sizes must be recomputed inside each new component.
2. 2. Why a centroid exists. If a candidate has a neighboring component larger than half, move into that component. There is at most one such neighbor. After moving, the component behind you is smaller than half, so you cannot move back; in a tree the process cannot revisit vertices. It must stop at a candidate with no oversized side. Our implementation instead checks all candidates after one size pass, also taking linear time per component.
3. 3. Remove the separator and continue. Mark centroid c as blocked and set centroidParent[c] to the centroid that created this component, or 0 at the top. Each remaining active neighbor starts a separate component. Decompose them all, making their top centroids children of c. Original adjacency lists never change; the blocked array represents removal. Edges of the centroid hierarchy need not be original tree edges. The pending-task stack makes this procedure iterative.
4. 4. Trace a five-vertex path. For 1–2–3–4–5, the first centroid is 3, splitting {1,2} and {4,5}. Either vertex of a two-vertex component is valid. The code chooses the smallest eligible label, giving centroids 1 and 4. Thus centroidParent[3]=0, [1]=3, [2]=1, [4]=3, [5]=4. This tie-break only makes output reproducible; any centroid choice has the same asymptotic guarantees.
5. 5. Prove the build complexity. Every child component has at most half the size of its parent component. A vertex belongs to O(log N) successive components before becoming a centroid itself. At a fixed hierarchy depth, components are disjoint, so scanning and sizing them costs O(N) altogether. Summing over depths gives O(N log N). Component collection and size calculation are iterative, so even an original path does not overflow the C++ call stack.
6. 6. Understand a typical application. For nearest activated-vertex queries, precompute distances from each vertex to its centroid ancestors. Store best[c], the shortest distance from c to an activated vertex in its decomposition region. Activating v updates best[c] using dist(v,c) for each centroid ancestor. Query x minimizes dist(x,c)+best[c] over its ancestors. Candidates are route lengths, so they cannot undercut the actual nearest distance. At the separator where x and a nearest activated vertex first split, the path passes through c and equality holds. With stored distances, activation and query take O(log N), using O(N log N) space. Deletions need additional structures. The runnable program builds the hierarchy prerequisite, not the query layer.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<bool>blocked(n+1,false);
    vector<int>localParent(n+1),sz(n+1),centroidParent(n+1);
    vector<pair<int,int>>tasks{{1,0}};
    while(!tasks.empty()){
        auto[start,above]=tasks.back();
        tasks.pop_back();
        // Collect only this active component, ignoring earlier separators.
        vector<int>component{start};
        localParent[start]=0;
        for(int i=0;i<(int)component.size();i++){
            int v=component[i];
            for(int u:g[v]){
                if(!blocked[u]&&u!=localParent[v]){
                    localParent[u]=v;
                    component.push_back(u);
                }
            }
        }
        int total=(int)component.size();
        for(int v:component){
            sz[v]=1;
        }
        for(int i=total-1;i>0;i--){
            int v=component[i];
            sz[localParent[v]]+=sz[v];
        }
        int centroid=n+1;
        for(int v:component){
            int largest=total-sz[v]; // Parent-side component.
            for(int u:g[v]){
                if(!blocked[u]&&localParent[u]==v){
                    largest=max(largest,sz[u]);
                }
            }
            if(largest<=total/2){
                centroid=min(centroid,v);
            }
        }
        // Save a hierarchy edge; it need not be an original tree edge.
        centroidParent[centroid]=above;
        // Removing the centroid creates independent components for later tasks.
        blocked[centroid]=true;
        for(int u:g[centroid]){
            if(!blocked[u]){
                tasks.push_back({u,centroid});
            }
        }
    }
    for(int v=1;v<=n;v++){
        cout<<centroidParent[v]<<(v==n?'\n':' ');
    }
}

Complexity analysis

O(N log N) build time: each component is processed linearly, components at one depth are disjoint, and sizes halve down the hierarchy. O(N) auxiliary space for this builder. Storing every vertex-to-centroid-ancestor distance for applications takes O(N log N) space.

Example input and output

N then N−1 undirected edges. Output centroidParent[1..N], with 0 for the hierarchy root.

Input

5
1 2
2 3
3 4
4 5

Output

3 1 0 3 4

Vertex 3 is the top centroid; ties use the smallest eligible label.

Practical applications

Nearest activated vertex, counting paths of a chosen length, and divide-and-conquer on paths. For counting, process pairs crossing the centroid first and leave pairs entirely in one component to its recursive subproblem.

Check your understanding

What defines a centroid of an M-vertex component?

Put it into practice

Print each vertex’s depth in the centroid hierarchy.