Heavy-Light Decomposition (HLD)¶

Algorithm Steps¶

1. Heavy Edge Identification: For each node, determine its child with the maximum subtree size (heavy child).

2. Chain Decomposition: Connect heavy edges to form chains. Each light edge starts a new chain.

3. Assign Headers: Mark the topmost node of each chain.

4. Coordinate Compression: Map tree nodes to a linear array while preserving chain continuity.

Implementation¶

The following code shows LCA (Lowest Common Ancestor) finding using HLD:

int lca(int u, int v) {  // This function finds LCA using HLD decomposition
    while(head[u] != head[v]) {  // Traverse up chains until common header
        if(depth[head[u]] < depth[head[v]])
            swap(u, v);
        u = parent[head[u]];  // Jump to parent of current chain's header
    }
    return depth[u] < depth[v] ? u : v;  // Return deeper node from final chain
}

Key Properties¶

• Path between any two nodes contains O(log n) light edges

• Each chain corresponds to a continuous segment in the linear array

• Query complexity reduces to O(log²n) when combined with segment trees

Applications¶

• Path sum/maximum queries

• Subtree updates

• Network flow optimizations

• Dynamic connectivity maintenance

Definition¶

A classical method similar to Sack for answering path-related queries in trees. The main problem of HLD in a rooted tree is partitioning the tree’s vertices into a number of upward chains such that when moving from any leaf toward the root, the vertices encounter at most \(O(lg(n))\) paths.

Decomposition Algorithm¶

First, we root the tree from vertex one and compute the size of each vertex's subtree (\(sz[i]\)) in linear time. Now, starting from the root, we perform a \(dfs\) and find the chains such that the vertices of each \(chain\) form a consecutive interval of the vertices we visit. If the current vertex (v) has a child whose size is greater than or equal to \(sz[v]/2\), we move to that vertex and continue the chain of vertex v from that child. (If no such vertex exists, we end the chain of vertex v here.) Then, we perform a dfs from the remaining children of the current vertex and start a new chain from each of them.

int sz[N]; // Subtree sizes
vector<int> adj[N];

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

void dfs_hld(int v, int p) {
    // Heavy child
    int heavy = -1;
    for (int u : adj[v]) {
        if (u != p && (heavy == -1 || sz[u] > sz[heavy]))
            heavy = u;
    }

    for (int u : adj[v]) {
        if (u != p) {
            if (u == heavy) {
                // Continue current chain
                head[u] = head[v];
            } else {
                // Start new chain
                head[u] = u;
            }
            dfs_hld(u, v);
        }
    }
}

// Other children
dfs_hld(1, -1);

Correctness Proof¶

Starting from an arbitrary vertex, we move upward toward the root. We define variable \(X\) to be the size of the current vertex's subtree. Each time we move upward toward the root (from v to u) and enter a new chain, \(X\) at least doubles. Otherwise, \(sz[v]*2>sz[u]\) would hold, meaning vertex v is part of vertex u's chain, and moving upward would not lead us into a new chain.

There exists an optimization in partitioning that does not necessarily improve runtime but, as evident from the proof, certainly does not worsen it. During partitioning, if a vertex v has no child with size at least half of v's size and is not a leaf (i.e., has at least one child), instead of terminating the chain at this vertex, we continue it through its largest child (i.e., we assume the size of its largest child is at least half of \(sz[v]\)).

Algorithm Implementation¶

 1def bfs(graph, start):
 2    # Top-down approach using an adjacency matrix
 3    visited = [False] * len(graph)  # Initialize visited list
 4    queue = []  # Create empty queue
 5
 6    visited[start] = True
 7    queue.append(start)
 8
 9    while queue:
10        node = queue.pop(0)
11        print(node, end=" ")
12
13        # Check neighboring nodes
14        for neighbor in range(len(graph[node])):
15            # Check if a node is visited
16            if graph[node][neighbor] == 1 and not visited[neighbor]:
17                visited[neighbor] = True
18                queue.append(neighbor)

In the above implementation, the BFS function is implemented using a queue and a list to track visited nodes. The graph is represented as an adjacency matrix where the value 1 indicates an edge between two nodes. This implementation follows the standard BFS approach where nodes are visited level by level.

The time complexity of the BFS algorithm is O(V + E) where V is the number of nodes and E is the number of edges in the graph. Note that in line 12, checking all neighbors of a node is done through examining the adjacency matrix row corresponding to that node.

const int MAXN = 100010;

int n, m, k, u, v, x, y;
int par[MAXN], sz[MAXN], h[MAXN], head[MAXN];
int stt[MAXN], fnt[MAXN], timer = 1;

int dfs1(int node){ // finding subtree sizes
        h[node] = h[par[node]] + 1;
        for(int v: G[node])
                if(v != par[node]){
                        par[v] = node;
                        sz[node] += dfs1(v);
                }
        return ++sz[node];
}
void dfs2(int node, int hd){
        head[node] = hd;
        stt[node] = timer++;
        int big = 0;
        for(int v: G[node]) if(v != par[node] && sz[big] < sz[v]) big = v;
        if(big) dfs2(big, hd);
        for(int v: G[node]) if(v != par[node] && v != big) dfs2(v, v);
        fnt[node] = timer;
}

int main(){
        cin >> n;
        for (int i = 1; i < n; i++){
                cin >> u >> v;
                G[u].push_back(v);
                G[v].push_back(u);
        }
        dfs1(1);
        dfs2(1, 1);
        return 0;
}

Here, each chain forms an interval of vertices based on starting time. Thus, for various problems, we can build a data structure like a segment tree on this order and reduce path queries to \(O(\lg(n))\) operations on that data structure. (In most trees, this value is much less than \(\lg(n)\).)

Additionally, with this implementation, we can also answer subtree queries!