Python Program for Heavy-Light Decomposition (HLD)

Heavy-Light Decomposition is an advanced technique used to break a tree into chains to efficiently answer path queries.

It is commonly used with segment trees or binary indexed trees for fast updates and queries on trees.

1. Understanding the Problem

Given a tree, efficiently process queries like sum, max, or minimum on the path between two nodes.

Query: Find sum from node 4 to node 7
Goal: Answer in O(log^2 n)

2. Method 1: Basic Concept

# Heavy-Light Decomposition idea:
# - Each node selects one heavy child (largest subtree)
# - Remaining edges are light
# - Forms chains for efficient traversal

The tree is divided into heavy paths to reduce query complexity.

3. Method 2: DFS for Subtree Sizes

def dfs(u, parent):
    size[u] = 1
    max_subtree = 0

    for v in tree[u]:
        if v != parent:
            dfs(v, u)
            size[u] += size[v]

            if size[v] > max_subtree:
                max_subtree = size[v]
                heavy[u] = v

This step identifies heavy edges based on subtree size.

4. Method 3: Decompose Tree

def decompose(u, head_node):
    head[u] = head_node
    pos[u] = current_pos[0]
    current_pos[0] += 1

    if heavy[u] != -1:
        decompose(heavy[u], head_node)

    for v in tree[u]:
        if v != parent[u] and v != heavy[u]:
            decompose(v, v)

Assigns nodes to chains and positions for segment tree mapping.

5. Method 4: Query on Path

def query(u, v):
    res = 0
    while head[u] != head[v]:
        if depth[head[u]] < depth[head[v]]:
            u, v = v, u
        res += segment_query(pos[head[u]], pos[u])
        u = parent[head[u]]

    if depth[u] > depth[v]:
        u, v = v, u

    res += segment_query(pos[u], pos[v])
    return res

Breaks the path into segments and queries efficiently.

6. Method 5: Handling Edge Cases

n = int(input())

if n == 0:
    print("Empty tree")
elif n == 1:
    print("Single node tree")
else:
    print("Proceed with HLD")

Handles special cases like empty or single-node trees.

7. Algorithm

1. Perform DFS to compute subtree sizes.

2. Identify heavy edges.

3. Decompose tree into chains.

4. Map nodes to segment tree indices.

5. Process queries using chain jumps.

8. Common Mistakes

1. Incorrect heavy child selection.

2. Wrong chain decomposition.

3. Improper indexing.

4. Forgetting segment tree integration.

9. Applications

1. Tree path queries.

2. Competitive programming.

3. Network routing analysis.

4. Graph-based data processing.

Conclusion

Heavy-Light Decomposition is a powerful technique for handling complex tree queries efficiently.

When combined with segment trees, it provides fast query and update operations.