Introduction

Heavy-light decomposition (HLD) is a sophisticated algorithmic technique used to partition tree structures into linear sequences, enabling efficient query and update operations. This method is particularly effective for handling subtree and path queries on trees.

Core Definitions

1. Heavy Child: For any node, its heavy child is the child node with the largest subtree.
2. Light Child: All non-heavy child nodes of a parent node.
3. Heavy Edge: An edge connecting a node to its heavy child.
4. Light Edge: An edge connecting a node to its light child.
5. Heavy Path: A path composed entirely of heavy edges. Single nodes also form trivial heavy paths.

Key Properties

• Every node belongs to exactly one heavy path.
• Subtree sizes reduce by at least half when tarversing light edges.
• Any path between two nodes can be divided into at most log(n) heavy paths.

Implementation Variables

void dfs1(int node, int parent) {
    siz[node] = 1;
    fa[node] = parent;
    dep[node] = dep[parent] + 1;
    
    for (int i = head[node]; i; i = edges[i].next) {
        int child = edges[i].v;
        if (child == parent) continue;
        
        dfs1(child, node);
        siz[node] += siz[child];
        if (siz[child] > siz[son[node]]) {
            son[node] = child;
        }
    }
}

void dfs2(int node, int chainTop) {
    top[node] = chainTop;
    dfn[node] = ++dfnCounter;
    rev[dfnCounter] = node;
    
    if (!son[node]) return;
    
    dfs2(son[node], chainTop);
    
    for (int i = head[node]; i; i = edges[i].next) {
        int child = edges[i].v;
        if (child != fa[node] && child != son[node]) {
            dfs2(child, child);
        }
    }
}

Segment Tree Implementation

struct SegmentTree {
    int sum[N<<2], maxVal[N<<2];
    
    void update(int o, int l, int r, int idx, int val) {
        if (l == r) {
            sum[o] = maxVal[o] = val;
            return;
        }
        
        if (idx <= mid) 
            update(ls, l, mid, idx, val);
        else 
            update(rs, mid+1, r, idx, val);
            
        pushUp(o);
    }
    
    int querySum(int o, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return sum[o];
        
        int res = 0;
        if (ql <= mid) res += querySum(ls, l, mid, ql, qr);
        if (qr > mid) res += querySum(rs, mid+1, r, ql, qr);
        return res;
    }
    
    int queryMax(int o, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return maxVal[o];
        
        int res = -INF;
        if (ql <= mid) res = max(res, queryMax(ls, l, mid, ql, qr));
        if (qr > mid) res = max(res, queryMax(rs, mid+1, r, ql, qr));
        return res;
    }
};

Path Query Functions

int pathSum(int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += tree.querySum(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res += tree.querySum(1, 1, n, dfn[u], dfn[v]);
    return res;
}

int pathMax(int u, int v) {
    int res = -INF;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res = max(res, tree.queryMax(1, 1, n, dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res = max(res, tree.queryMax(1, 1, n, dfn[u], dfn[v]));
    return res;
}