Heavy Light Decomposition

📌 Table of Contents

1. Problem

You are given a tree consisting of n nodes. The nodes are numbered 1,2,...,n. Each node has a value. Your task is to process following types of queries:

Solution: We will use Heavy-Light Decomposition (HLD) - a technique used to efficiently handle queries (such as max, xor, sum, …) on the path between any two nodes in a tree. A naive solution requires traversing the entire path, which can take O(n) in the worst case. Heavy-Light Decomposition (HLD) provides a way to reduce this to O(log² n) per query.

Prerequisite knowledge:

2. Idea behind

How it works?

Why choose the largest child?

Suppose a node u has a subtree of size sz[u].

This ensures:

đź’ˇ In other words:

Convex vs Concave

Build chains:

Consecutive heavy edges are connected to form a chain, and each chain is compressed into a continuous segment of an array (using Euler Tour + position numbering pos[] ) to reduce time complexity.

→ Then, instead of querying directly on the tree, we only need to query over contiguous array ranges.

3. Template

Initialization and Input


#include <iostream>
#include <vector>
#define pp push_back
using namespace std;
using ll = long long;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e5+5;

int n,q;
int sz[maxn],h[maxn],par[maxn],head[maxn],id[maxn],pos[maxn],a[maxn];
// sz[u]   = size of subtree rooted at u
// h[u]    = depth of u
// par[u]  = parent of u
// head[c] = head node of chain c
// id[u]   = which chain node u belongs to
// pos[u]  = position of u in the segment tree
// a[u]    = initial value of node u

int curchain,curpos; // track current chain index and position
vector<int> adj[maxn];
int st[4*maxn]; // segment tree

void input()
{
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>a[i]; // initial values
    for(int i=1,u,v;i<n;++i)
    {
        cin>>u>>v;
        adj[u].pp(v);
        adj[v].pp(u);
    }
    DFS(1,0); // prepare size, depth, parent
    curpos=curchain=1;
    HLD(1,0); // build decomposition

    for(int i=1,t,u,v;i<=q;++i)
    {
        cin>>t>>u>>v;
        if(t==1) udt(1,1,n,pos[u],v); // point update on node u
        else cout<<solve(u,v)<<sp;     // query max on path u→v
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    return 0;
}
        

-----------------------------------------------------------------

Depth-first search: to pre-compute subtree sizes (to pick heavy child), depths, and parents.


void DFS(int u, int v)
{
    h[u]=h[v]+1;   // depth[u] = depth[parent]+1
    sz[u]=1;
    par[u]=v;
    for(int i:adj[u])
    {
        if(i==v) continue;
        DFS(i,u);
        sz[u]+=sz[i]; // accumulate size
    }
}
        

-----------------------------------------------------------------

Segment Tree: for point update + range maximum query


void udt(int id, int l, int r, int u, int v)
{
    if(l>u or r<u)  return;         // outside the update position
    if(l==r) st[id]=v;              // leaf node, assign value
    else
    {
        int mid=(l+r)/2;
        udt(id*2,l,mid,u,v);
        udt(id*2+1,mid+1,r,u,v);
        st[id]=max(st[id*2],st[id*2+1]); // recalc parent node
    }
}

int gt(int id, int l, int r, int u, int v)
{
    if(l>v or r<u)  return 0;       // outside range
    if(l>=u && r<=v) return st[id]; // fully inside range
    else
    {
        int mid=(l+r)/2;
        return max(gt(id*2,l,mid,u,v), gt(id*2+1,mid+1,r,u,v));
    }
}
        

-----------------------------------------------------------------

Heavy-Light Decomposition: to build chains and map nodes to segment tree positions.

👉 Key idea:


void HLD(int u, int v)
{
    if(head[curchain]==0) head[curchain]=u; // new chain → assign head
    id[u]=curchain;                          // mark chain of u
    pos[u]=curpos;                           // position in segtree
    udt(1,1,n,curpos,a[u]);                  // insert value into segtree
    ++curpos;

    int tmp=0; // tmp = heavy child
    for(int i:adj[u])
    {
        if(i==v) continue;
        if(sz[tmp]<sz[i]) tmp=i; // pick child with largest subtree
    }
    if(tmp!=0) HLD(tmp,u); // continue heavy edge in same chain

    for(int i:adj[u]) // process light edges
    {
        if(i!=v && i!=tmp)
        {
            ++curchain;      // new chain
            HLD(i,u);        // decompose light child
        }
    }
}
        

-----------------------------------------------------------------

Query on path u → v: find maximum value on path u → v


int solve(int u, int v)
{
    int ans=0;
    while(id[u]!=id[v]) // while not in the same chain
    {
        if(id[u]<id[v]) swap(u,v); 
        // query from head of u’s chain to u
        ans=max(ans, gt(1,1,n,pos[head[id[u]]], pos[u]));
        u=par[head[id[u]]]; // move u up to parent of its chain head
    }
    if(h[u]>h[v]) swap(u,v); // now same chain → query directly
    ans=max(ans, gt(1,1,n,pos[u],pos[v]));
    return ans;
}
        

4. Problem set