Hierarchical Graph Decompositions: Heavy-Light & Centroid Trees in Contest Programming

The Limits of Flat Tree Algorithms

In competitive programming contests (ICPC Regionals, Codeforces Div 1, IOI), problems frequently ask us to maintain dynamic trees under edge weight updates, path aggregates, or distance counting.

While array problems can be solved in $O(N \log N)$ using Segment Trees or Fenwick Trees, trees introduce structural complexity:

• Path queries ($u \to v$) cross arbitrary branches.
• Naive tree traversal takes $O(N)$ time per query, yielding $O(N \cdot Q)$ overall, which results in Time Limit Exceeded (TLE) when $N, Q \le 2 \times 10^5$.
• Simple binary lifting can answer static LCA and path minima in $O(\log N)$, but cannot support arbitrary range updates and dynamic point modifications.

To bridge the gap between trees and linear interval structures, two hierarchical graph decomposition paradigms reign supreme:

1. Heavy-Light Decomposition (HLD): Partitions tree vertices into linear chains for segment tree path queries.
2. Centroid Decomposition: Recursively divides trees at centroid vertices to solve divide-and-conquer path counting problems.

---

Heavy-Light Decomposition (HLD)

HLD partitions the vertices of an arbitrary rooted tree into disjoint chains such that any path from any node $u$ to the root passes through at most $O(\log N)$ distinct chains.

Definitions: Heavy vs. Light Edges

Let $size(u)$ denote the number of vertices in the subtree rooted at $u$.

• For any non-leaf node $u$, let $v$ be the child of $u$ with the maximum subtree size: $$v = \arg\max_{c \in \text{children}(u)} size(c)$$
• The edge $(u, v)$ is declared the Heavy Edge.
• All other edges from $u$ to its remaining children are declared Light Edges.
• A maximal path consisting entirely of heavy edges is called a Heavy Chain.

       (1) [size=9]
       / \
(light)/   \ (heavy)
     (2)   (3) [size=7]
           / \
    (heavy)/   \ (light)
         (4)   (5)

The Light Edge Crossing Theorem

Theorem: Any path from any vertex $u$ to the root contains at most $\lfloor \log_2 N \rfloor$ light edges.

Proof: When ascending from a child $c$ to its parent $p$ across a light edge, the subtree size at least doubles: $$size(p) \ge size(c) + size(\text{heavy_child}(p)) + 1 > 2 \cdot size(c)$$ Since the maximum possible subtree size is $N$, one can double the subtree size at most $\log_2 N$ times before reaching the root. Therefore, any simple path between any pair of vertices $(u, v)$ traverses at most $2 \lfloor \log_2 N \rfloor$ light edges and at most $2 \lfloor \log_2 N \rfloor + 1$ heavy chains.

---

Flattening the Tree with Euler Tour

To query heavy chains in $O(\log N)$ using a Segment Tree, we must map tree vertices to contiguous indices in an array $[0, N-1]$.

We perform two Depth-First Searches:

1. DFS 1 (dfs_sz): Computes subtree sizes, node depths, parent pointers, and identifies the heavy child for each vertex.
2. DFS 2 (dfs_hld): Visits heavy children first! This guarantees that every heavy chain occupies a strictly contiguous interval in the Euler tour time array tin[u].

vector<int> sz, parent_node, depth, heavy, head, tin;
int timer = 0;

void dfs_sz(int u, int p, int d) {
    sz[u] = 1;
    parent_node[u] = p;
    depth[u] = d;
    int max_c_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_sz(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > max_c_sz) {
            max_c_sz = sz[v];
            heavy[u] = v;
        }
    }
}

void dfs_hld(int u, int h) {
    head[u] = h;
    tin[u] = timer++;
    if (heavy[u] != -1) {
        // Visit heavy child immediately to keep chain indices contiguous!
        dfs_hld(heavy[u], h);
    }
    for (int v : adj[u]) {
        if (v != parent_node[u] && v != heavy[u]) {
            // Light child starts a brand new heavy chain
            dfs_hld(v, v);
        }
    }
}

Path Queries and Updates

When answering a query on the path between $u$ and $v$:

1. Compare the chain heads head[u] and head[v].
2. Move the node whose chain head is deeper upwards, querying the segment tree over [tin[head[u]], tin[u]].
3. Jump $u$ to parent_node[head[u]].
4. Repeat until both $u$ and $v$ reside on the same heavy chain, then query the final segment [min(tin[u], tin[v]), max(tin[u], tin[v])].

Total query time: $O(\log^2 N)$ segment tree operations.

---

Centroid Decomposition

Where HLD shines at dynamic path updates, Centroid Decomposition is the premier tool for static divide-and-conquer path counting problems (e.g., counting pairs of vertices with path distance $\le K$ or path weights satisfying a predicate).

Centroid Definition & Invariant

A vertex $C$ is a centroid of a tree with $M$ vertices if removing $C$ partitions the tree into a forest of subtrees, each containing at most $\lfloor M / 2 \rfloor$ vertices. Every tree has at least one and at most two centroids.

Building the Centroid Tree

1. Find the centroid $C$ of the current component in $O(M)$ time using DFS.
2. Mark $C$ as visited (decomposed).
3. Recursively compute the centroids of all adjacent subtrees, linking them as children of $C$ in the Centroid Tree.

Because the size of each component shrinks by at least half at each level: $$\text{Height of Centroid Tree} \le \lfloor \log_2 N \rfloor + 1$$

int get_centroid(int u, int p, int total_size) {
    for (int v : adj[u]) {
        if (v != p && !deleted[v] && sz[v] > total_size / 2) {
            return get_centroid(v, u, total_size);
        }
    }
    return u;
}

Solving "Paths with Length $K$":

For a centroid $C$, any path in the component either:

1. Passes through $C$: Can be calculated by combining paths originating from different subtrees connected to $C$.
2. Lies entirely within one of the subtrees: Handled recursively in subsequent decomposition steps.

By tracking path lengths from $C$ with a hash map or frequency array, we solve path counting across all pairs in $O(N \log N)$ or $O(N \log^2 N)$ without storing $O(N^2)$ distances.

Mastering these two paradigms equips contest programmers to tackle Codeforces 2400+ rating tree problems with systematic confidence.