1. The Intuition: Express Trains and Local Stops

Before we introduce mathematical formalism, let's build a mental model. Imagine the tree as a massive subway system. Nodes are stations, and edges are the tracks connecting them. If you want to travel from a station in the deep suburbs to a station on the other side of the city, taking a local train that stops at every single station (a standard graph traversal) takes $O(N)$ time.

To speed this up, the transit authority introduces Express Lines. An Express Line is a contiguous, non-branching track that goes straight towards the city center. When you travel, you ride the Express Line as far as you can. When the Express Line no longer takes you where you want to go, you step off, walk across the platform (a Local Transfer), and board another Express Line.

Heavy-Light Decomposition is the algorithm that designs this subway map. It intelligently assigns edges to be either "Heavy" (part of an Express Line) or "Light" (a Local Transfer). The magic of HLD is how it assigns these edges to guarantee that no matter which two stations you travel between, you will never have to make more than $O(\log N)$ local transfers.

2. Defining Heavy and Light Edges

2.1 Subtree Sizes

To determine which edges become heavy and which become light, we must first root the tree arbitrarily (node 0 or 1 is fine). We then run a Depth First Search (DFS) to calculate the subtree size of every node. The subtree size of node $u$, denoted as $size(u)$, is the total number of nodes in the subtree rooted at $u$, including $u$ itself.

2.2 The Selection Rule

For every non-leaf node $u$, we look at all of its immediate children. We find the child $v$ that has the strictly largest subtree size. (If there is a tie, we can pick any of the tied children).

• The edge from $u$ to this largest child $v$ is classified as a Heavy Edge.
• The edges from $u$ to all other children are classified as Light Edges.

Because every node selects exactly one Heavy Edge leading down to a child, these Heavy Edges naturally link together to form non-branching paths going down the tree. We call these Heavy Chains. A node that is connected to its parent via a Light Edge is considered the "head" of a new Heavy Chain.

2.3 The Core Theorem: Why $O(\log N)$ Light Edges?

If we walk from any node $u$ up to the root, how many Light Edges will we traverse? The mathematics is beautifully simple.

Suppose we traverse a Light Edge from node $v$ up to its parent $u$. Because the edge $(u, v)$ is Light, we know that $u$ must have some other child $w$ that was chosen as the Heavy child. By definition, $size(w) \ge size(v)$.

Therefore, the total size of the parent's subtree must be at least the size of $v$'s subtree plus the size of $w$'s subtree, plus the parent itself:

$$size(u) > size(v) + size(w) \ge 2 \times size(v)$$

This inequality is the secret to HLD. Every time we walk up a Light Edge, the size of the subtree we are standing in at least doubles. Since the maximum possible subtree size is $N$ (the total number of nodes in the tree), we can only double the size $\log_2(N)$ times before we hit the root. Therefore, any path from a node to the root contains at most $O(\log N)$ Light Edges!

Because Heavy Chains are contiguous segments, a path to the root consists of jumping up a Heavy Chain, taking a Light Edge transfer, jumping up the next Heavy Chain, and so on. This means the path is broken into at most $O(\log N)$ contiguous Heavy Chain segments.

3. The DFS Strategy: Flattening the Tree

We know that Heavy Chains are contiguous paths. To make Segment Trees work, nodes on the same Heavy Chain must be assigned contiguous indices in our 1D array. We achieve this using a very specific Depth First Search (DFS) order.

Standard DFS visits children in whatever order they appear in the adjacency list. For HLD, we modify our DFS to always visit the Heavy Child first, before visiting any Light Children. By diving down the Heavy Chain completely before backtracking, we ensure that all nodes in a Heavy Chain receive sequential DFS discovery timestamps.

3.1 The Two-Pass DFS Implementation

Implementation generally requires two DFS passes:

• DFS 1 (Information Gathering): Computes depths, parents, and subtree sizes. Crucially, it identifies the "heavy child" for each node and swaps it to the 0th index of the adjacency list so it gets visited first in the next pass.
• DFS 2 (Flattening): Traverses the tree, tracking the "head" (top-most node) of the current Heavy Chain. It assigns sequential array positions to nodes as it visits them.

vector<int> parent, depth, heavy, head, pos;
int current_pos = 0;

// DFS 1: Calculate subtree sizes and heavy edges
int dfs1(int v, int p) {
    int size = 1, max_child_size = 0;
    for (int c : adj[v]) {
        if (c != p) {
            parent[c] = v, depth[c] = depth[v] + 1;
            int c_size = dfs1(c, v);
            size += c_size;
            if (c_size > max_child_size) {
                max_child_size = c_size;
                heavy[v] = c; // Record the heavy child
            }
        }
    }
    return size;
}

// DFS 2: Assign segment tree positions and track chain heads
void dfs2(int v, int p, int chain_head) {
    head[v] = chain_head;     // The top of this node's express line
    pos[v] = current_pos++;   // Flattened array index
    
    if (heavy[v] != -1) {
        // ALWAYS visit heavy child first to keep the chain contiguous
        dfs2(heavy[v], v, chain_head);
    }
    
    for (int c : adj[v]) {
        if (c != p && c != heavy[v]) {
            // Light children start their own new chains
            dfs2(c, v, c);
        }
    }
}

4. Executing the Query

Once the tree is flattened, how do we query the path between $u$ and $v$? We use a technique similar to finding the Lowest Common Ancestor (LCA). We examine the `head` of the chains that $u$ and $v$ are currently on.

• If `head[u]` and `head[v]` are different, they are on different Express Lines. We take the node whose chain head is deeper in the tree (has a greater depth) and "jump" it up.
• We query the Segment Tree for the contiguous range from `pos[head[u]]` to `pos[u]`. (Because it's a Heavy Chain, they are contiguous in the array!)
• We then update $u$ to be `parent[head[u]]`, jumping across the Light Edge to the bottom of the next chain.
• We repeat this until $u$ and $v$ finally land on the exact same Heavy Chain (`head[u] == head[v]`).
• Once they are on the same chain, the path between them is just a single contiguous segment! We do one final Segment Tree query between `pos[u]` and `pos[v]` (making sure to query from the smaller position to the larger).

int query(int u, int v) {
    int res = 0; // Or -INFINITY for max queries
    // While they are on different chains...
    while (head[u] != head[v]) {
        // Force u to be the one deeper in the tree
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        
        // Query the segment tree for u's current chain
        res = combine(res, seg_query(pos[head[u]], pos[u]));
        
        // Jump u up to the parent of its chain head
        u = parent[head[u]];
    }
    
    // Now they are on the same chain.
    if (depth[u] > depth[v]) swap(u, v);
    
    // Final query for the segment between them
    res = combine(res, seg_query(pos[u], pos[v]));
    
    return res;
}

5. Frequently Asked Questions