Tree Chain Decomposition for Path Queries on Trees: A Complete Guide to Heavy-Light Decomposition

Tree chain decomposition, also known as Heavy-Light Decomposition (HLD), transforms any tree path query into O(log N) segment tree operations by splitting the tree into disjoint heavy chains, making it essential for competitive programming.

This technique bridges advanced data structures and graph theory, allowing you to solve complex path aggregation problems—such as sum, minimum, or XOR along arbitrary tree paths—efficiently. The hzwer/shareoi repository provides authoritative educational materials that explain both the theoretical foundations and practical implementations of tree chain decomposition.

How Tree Chain Decomposition Works

Heavy-Light Decomposition operates by classifying edges as either heavy or light based on subtree sizes, then grouping consecutive heavy edges into chains. This structure ensures that any root-to-leaf path contains at most O(log N) light edges.

Heavy Edge Selection

The first DFS traversal computes subtree sizes for every node. For each node, the child with the largest subtree size is designated as the heavy child, and the connecting edge becomes a heavy edge. All other edges are marked as light edges. This selection guarantees that any subtree reached via a light edge contains at most half the nodes of its parent subtree.

Building Heavy Paths

Heavy edges naturally form continuous chains. Starting from the root, you follow heavy edges downward until reaching a leaf or a node with no heavy child. This maximal sequence constitutes a heavy chain. Every node belongs to exactly one chain, and each chain has a head (the topmost node) that connects to the rest of the tree via a light edge (except the root chain).

Linearization and Chain Heads

During the second DFS (decomposition), each node is assigned a position index in a global linear array according to its order in the heavy chain. Because nodes in the same chain occupy contiguous indices, a path segment within a single chain maps to a simple range query on a segment tree or Binary Indexed Tree (BIT). The head array tracks the top node of each chain, enabling efficient upward jumps during query processing.

Answering Path Queries

To query the path between nodes u and v:

1. While head[u] and head[v] differ, the deeper chain head is farther from the root. Query the segment tree range from pos[head] to pos[node] for that chain, then move the node up to parent[head].
2. When both nodes share the same chain, they lie on a single heavy path. Query the final segment between their positions (ensuring correct order by depth).
3. Aggregate results from all queried segments.

Because each jump crosses a light edge, and any root-to-node path contains at most O(log N) light edges, the total query complexity is O(log² N) with a naive segment tree, or O(log N) with efficient range queries.

Implementing Tree Chain Decomposition in C++

Below is a complete, self-contained C++17 implementation that supports point updates and path sum queries. This code follows the exact structure used in competitive programming contests and aligns with the educational materials found in the hzwer/shareoi repository.

#include <bits/stdc++.h>
using namespace std;

/* ---------- Segment Tree (range sum) ---------- */
struct SegTree {
    int n; vector<long long> t;
    SegTree(int n = 0) { init(n); }
    void init(int n_) { n = n_; t.assign(4*n, 0); }
    void build(const vector<int>& a, int v, int tl, int tr) {
        if (tl == tr) t[v] = a[tl];
        else {
            int tm = (tl+tr)/2;
            build(a, v*2, tl, tm);
            build(a, v*2+1, tm+1, tr);
            t[v] = t[v*2] + t[v*2+1];
        }
    }
    void build(const vector<int>& a) { build(a,1,0,n-1); }
    void update(int v, int tl, int tr, int pos, long long val) {
        if (tl == tr) t[v] = val;
        else {
            int tm = (tl+tr)/2;
            if (pos <= tm) update(v*2, tl, tm, pos, val);
            else update(v*2+1, tm+1, tr, pos, val);
            t[v] = t[v*2] + t[v*2+1];
        }
    }
    void update(int pos, long long val) { update(1,0,n-1,pos,val); }
    long long query(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (l==tl && r==tr) return t[v];
        int tm = (tl+tr)/2;
        return query(v*2, tl, tm, l, min(r,tm))
             + query(v*2+1, tm+1, tr, max(l,tm+1), r);
    }
    long long query(int l, int r) { return query(1,0,n-1,l,r); }
};

/* ---------- Heavy‑Light Decomposition ---------- */
struct HLD {
    int N, timer = 0;
    vector<vector<int>> g;
    vector<int> parent, depth, heavy, head, pos, sz;
    vector<int> value;
    SegTree seg;

    HLD(int n = 0) { init(n); }

    void init(int n) {
        N = n; g.assign(N, {}); parent.assign(N,-1);
        depth.assign(N,0); heavy.assign(N,-1);
        head.assign(N,0); pos.assign(N,0); sz.assign(N,0);
        value.assign(N,0);
    }

    void addEdge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }

    int dfs(int v,int p){
        parent[v]=p; sz[v]=1; int maxsz=0;
        for(int to:g[v]) if(to!=p){
            depth[to]=depth[v]+1;
            int sub=dfs(to,v);
            sz[v]+=sub;
            if(sub>maxsz){ maxsz=sub; heavy[v]=to; }
        }
        return sz[v];
    }

    void decompose(int v,int h){
        head[v]=h; pos[v]=timer++;
        if(heavy[v]!=-1) decompose(heavy[v],h);
        for(int to:g[v]) if(to!=parent[v] && to!=heavy[v])
            decompose(to,to);
    }

    void build(const vector<int>& initVal){
        value = initVal;
        dfs(0,-1);
        decompose(0,0);
        seg.init(N);
        vector<int> arr(N);
        for(int i=0;i<N;i++) arr[pos[i]]=value[i];
        seg.build(arr);
    }

    void updateNode(int v,int val){
        seg.update(pos[v], val);
    }

    long long queryPath(int u,int v){
        long long res=0;
        while(head[u]!=head[v]){
            if(depth[head[u]]<depth[head[v]]) swap(u,v);
            int h=head[u];
            res+=seg.query(pos[h], pos[u]);
            u=parent[h];
        }
        if(depth[u]>depth[v]) swap(u,v);
        res+=seg.query(pos[u], pos[v]);
        return res;
    }
};

/* ---------- Example usage ---------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if(!(cin>>n>>m)) return 0;
    HLD hld(n);
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v; --u;--v;
        hld.addEdge(u,v);
    }
    vector<int> init(n);
    for(int i=0;i<n;i++) cin>>init[i];
    hld.build(init);
    while(m--){
        int type;cin>>type;
        if(type==1){
            int x,val;cin>>x>>val; --x;
            hld.updateNode(x,val);
        }else{
            int u,v;cin>>u>>v; --u;--v;
            cout<<hld.queryPath(u,v)<<"\n";
        }
    }
    return 0;
}

Code Structure Overview

• dfs(int v, int p): Computes sz[v] (subtree size) and identifies heavy[v] (the child with maximum subtree size).
• decompose(int v, int h): Assigns head[v] (chain head) and pos[v] (linear index). Recursively processes heavy children first to maintain contiguity, then spawns new chains for light children.
• queryPath(int u, int v): The core HLD logic. While u and v are on different chains, it queries the segment from head to the node on the deeper chain, then jumps to the parent of that head. Finally, it queries the remaining segment when both nodes share a chain.

Learning Resources from the hzwer/shareoi Repository

The hzwer/shareoi repository contains curated educational materials that explain tree chain decomposition from both theoretical and applied perspectives. These resources are referenced in the repository's README.md and provide the foundation for the implementation above.

• Data Structure Lecture: 树链剖分_王天懿.ppt (located in 数据结构/) provides a rigorous explanation of heavy edge selection, chain construction, and the mathematical proof that guarantees O(log N) query complexity.

• Graph Theory Applications: 树链剖分及其应用_蒋一瑶.pptx (located in 图论/) demonstrates concrete competitive programming scenarios, including path sum queries, subtree aggregations, and integration with Lowest Common Ancestor (LCA) algorithms.

Both files are indexed in the repository's documentation, making them accessible starting points for mastering tree chain decomposition.

Summary

• Tree chain decomposition (Heavy-Light Decomposition) partitions a tree into disjoint heavy paths such that any root-to-node path crosses at most O(log N) light edges.
• Construction requires two DFS passes: one to calculate subtree sizes and identify heavy children, and another to assign chain heads and linear positions.
• Query processing reduces path aggregation to O(log N) segment tree or BIT operations by climbing chain heads until both nodes share a chain.
• The hzwer/shareoi repository provides authoritative slide decks (树链剖分_王天懿.ppt and 树链剖分及其应用_蒋一瑶.pptx) that detail both the theory and competitive programming applications.

Frequently Asked Questions

What is the time complexity of tree chain decomposition?

Building the decomposition requires O(N) time for the two DFS traversals and O(N) to build the segment tree. Each path query or point update operates in O(log² N) in the worst case, though with careful implementation using iterative segment trees this becomes O(log N). The key insight is that any path contains at most O(log N) light edges, and each heavy chain segment is queried in O(log N) time.

How does tree chain decomposition differ from Euler tour techniques?

Euler tour techniques flatten the entire subtree into a contiguous range, making subtree queries efficient (O(1) or O(log N)) but path queries difficult (requiring additional data structures like binary lifting). Tree chain decomposition specifically optimizes for path queries by ensuring that nodes on the same heavy chain occupy contiguous indices, allowing path aggregation via segment tree ranges. While Euler tours excel at subtree problems, HLD is the standard solution for path-related queries on trees.

Can tree chain decomposition handle subtree queries?

Yes, although it is primarily designed for path queries, tree chain decomposition can handle subtree queries with a minor modification. During the initial DFS, if you assign positions using a standard preorder traversal (where the subtree of node v corresponds to the range [pos[v], pos[v] + sz[v] - 1]), you can query the entire subtree as a single range on the segment tree. The hzwer/shareoi slides in 树链剖分及其应用_蒋一瑶.pptx specifically demonstrate how to unify path and subtree queries within the same HLD framework.

Where can I find competitive programming problems to practice HLD?

The hzwer/shareoi repository references classic problems that appear in Chinese OI (Olympiad in Informatics) contests and international competitions. Look for problems tagged with "tree chain decomposition," "HLD," or "heavy-light" on platforms like Codeforces, AtCoder, and Luogu. Common problem types include maintaining path sums with node updates (similar to the provided C++ template), finding the maximum edge weight on a path, and counting distinct colors on tree paths— all of which are covered in the repository's slide decks.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}