v. Heavy-Light and Long-Path Decomposition

Heavy-light: every vertex continues its chain into the child with the largest subtree. Any root path crosses $O(\log n)$ chains, chains and subtrees are contiguous in one array, so path updates and queries become $O(\log n)$ range operations ($O({\log }^{2}n)$ with a segment tree). Long-path: continue into the child of greatest height instead; then depth-indexed DP arrays can be inherited in $O(1)$, for $O(n)$ total.

Heavy-light decomposition

struct HLD {
    int n; vector<int> par, dep, heavy, head, pos, sub, at;    // vertex v sits at position pos[v]; at = inverse
    HLD(const vector<vector<int>>& adj, int root) : n(sz(adj)), par(n, -1), dep(n), heavy(n, -1), head(n), pos(n), sub(n, 1), at(n) {
        vector<int> order{root};
        for (int i = 0; i < n; i++) for (int v : adj[order[i]]) if (v != par[order[i]]) par[v] = order[i], dep[v] = dep[order[i]] + 1, order.push_back(v);
        for (int i = n - 1; i > 0; i--) sub[par[order[i]]] += sub[order[i]];
        for (int u = 0; u < n; u++) for (int v : adj[u]) if (v != par[u] && (heavy[u] < 0 || sub[v] > sub[heavy[u]])) heavy[u] = v;
        int cur = 0; vector<int> st{root}; head[root] = root;
        while (sz(st)) {                                     // heavy child popped right after its parent
            int u = st.back(); st.pop_back(); at[pos[u] = cur++] = u;
            for (int v : adj[u]) if (v != par[u] && v != heavy[u]) head[v] = v, st.push_back(v);
            if (heavy[u] >= 0) head[heavy[u]] = head[u], st.push_back(heavy[u]);
        }
    }
    template <class F> void path(int u, int v, bool edges, F f) {   // f(l, r): half-open position ranges, any order
        for (; head[u] != head[v]; v = par[head[v]]) { if (dep[head[u]] > dep[head[v]]) swap(u, v); f(pos[head[v]], pos[v] + 1); }
        if (dep[u] > dep[v]) swap(u, v);
        if (pos[u] + edges <= pos[v]) f(pos[u] + edges, pos[v] + 1);   // edges: skip the LCA (edge value stored at child)
    }
    pair<int, int> subtree(int v) const { return {pos[v], pos[v] + sub[v]}; }
    int lca(int u, int v) const {
        for (; head[u] != head[v]; v = par[head[v]]) if (dep[head[u]] > dep[head[v]]) swap(u, v);
        return dep[u] < dep[v] ? u : v;
    }
    vector<tuple<int, int, bool>> orderedPath(int u, int v, bool edges) const {   // segments in walk order u -> v
        vector<tuple<int, int, bool>> A, B;                  // (l, r, up): up = walk positions r-1 down to l
        while (head[u] != head[v]) {
            if (dep[head[u]] >= dep[head[v]]) A.push_back({pos[head[u]], pos[u] + 1, true}), u = par[head[u]];
            else B.push_back({pos[head[v]], pos[v] + 1, false}), v = par[head[v]];
        }
        if (dep[u] >= dep[v]) { if (pos[v] + edges <= pos[u]) A.push_back({pos[v] + edges, pos[u] + 1, true}); }
        else if (pos[u] + edges <= pos[v]) B.push_back({pos[u] + edges, pos[v] + 1, false});
        A.insert(A.end(), B.rbegin(), B.rend());
        return A;
    }
    int kthOnPath(int u, int v, int k) const {               // vertex at distance k from u towards v, -1 if too far
        for (auto [l, r, up] : orderedPath(u, v, false)) {
            if (k < r - l) return at[up ? r - 1 - k : l + k];
            k -= r - l;
        }
        return -1;
    }
};

Usage with any range structure: hld.path(u, v, false, [&](int l, int r) { seg.update(l, r, x); }); and the same lambda accumulating a sum or max for queries; subtree(v) for subtree operations on the same array. For non-commutative combines (matrix products, hashes of the path string, “first vertex with property”), use orderedPath and query each segment in its direction: keep two aggregates per segment-tree node, one left-to-right and one right-to-left.

Detail	Rule
values on edges	store at the child endpoint, pass edges = true to skip the LCA
path + subtree on one array	positions are a DFS preorder: subtree($v$) $=[{\text{pos}}_v,{\text{pos}}_v+{\text{sub}}_v)$
complexity	$O(\log n)$ segments per path; $O({\log }^{2}n)$ with a segment tree
root-path queries only, static values	prefix sums per chain: $O(\log n)$
path + subtree with rerooting	reroot formulas from Euler Tour apply to pos too
changing tree shape	Link-Cut Tree
true $O(\log n)$ path queries, idempotent op, no updates	sparse table per chain
true $O(\log n)$ with updates	link-cut trees, or a global balanced BST over chains — rarely worth the complexity over $O({\log }^{2}n)$

Need	Structure	Complexity
LCA only	binary lifting	$O(\log n)$
Path queries, static tree	binary lifting with aggregates	$O(\log n)$
Path queries and updates, static tree	HLD + lazy segtree	$O({\log }^{2}n)$
Subtree queries and updates	Euler tour + segment tree	$O(\log n)$
Tree changes (link/cut)	link-cut tree	$O(\log n)$ amortized
Path counting / distance problems	centroid decomposition	$O(n\log n)$
Queries on a small vertex subset	virtual tree	$O(k\log n)$

HLD is the workhorse of this list: static tree, path updates and queries, $O({\log }^{2}n)$, about 60 lines.

Proof: $O(\log n)$ chains, contiguity, correctness of the walks

Light edges: if $v$ is a light child of $u$, then ${\text{sub}}_v\le {\text{sub}}_{\text{heavy}(u)}$ and both are inside $u$‘s subtree, so $2{\text{sub}}_v\le {\text{sub}}_u-1$. Walking up a root path, every light edge at least doubles the subtree size, so there are $\le {\log }_{2}n$ of them, and the path meets $\le {\log }_{2}n+1$ chains. Contiguity: the stack pops a vertex’s heavy child immediately after it, so chains get consecutive positions, and it finishes a whole subtree before popping anything pushed earlier, so subtrees are contiguous (it is a preorder). Walks: let $u,v$ be on different chains with $\text{dep}({\text{head}}_v)\ge \text{dep}({\text{head}}_u)$, and let $\ell$ be their LCA. If $\ell$ were on $v$‘s chain between ${\text{head}}_v$ and $v$, then $u$ (a descendant of $\ell$ not on that chain, as the heads differ) would leave the chain below $\ell$ through a light edge, putting ${\text{head}}_u$ strictly below $\ell$ and hence deeper than ${\text{head}}_v$: contradiction. So the whole segment from ${\text{head}}_v$ to $v$ lies on the path strictly below $\ell$, and we jump to the head’s parent. When both are on one chain, the remaining part is the contiguous segment between them, and the shallower one is the LCA. Each iteration moves past a light edge, so there are $O(\log n)$ segments. orderedPath performs the same moves, collecting $u$‘s segments upward in order and $v$‘s segments in reverse.

Long-path decomposition

struct LongPath {
    int n; vector<vector<int>> adj; vector<int> parent, len, heavy, pos, order;   // len = height in vertices
    LongPath(const vector<vector<int>>& g, int root) : n(sz(g)), adj(g), parent(n, -1), len(n, 1), heavy(n, -1), pos(n) {
        vector<int> bfs{root};
        for (int i = 0; i < sz(bfs); i++) for (int u : adj[bfs[i]]) if (u != parent[bfs[i]]) parent[u] = bfs[i], bfs.push_back(u);
        for (int i = sz(bfs) - 1; i > 0; i--) { int v = bfs[i], p = parent[v]; if (len[v] + 1 > len[p]) len[p] = len[v] + 1, heavy[p] = v; }
        vector<int> st{root};
        while (sz(st)) {                                     // deepest child right after its parent
            int v = st.back(); st.pop_back(); pos[v] = sz(order); order.push_back(v);
            for (int u : adj[v]) if (u != parent[v] && u != heavy[v]) st.push_back(u);
            if (heavy[v] >= 0) st.push_back(heavy[v]);
        }
    }
};
// example: for each v, the smallest depth j maximising #{vertices at depth j below v} (CF "Dominant Indices")
vector<int> dominantIndices(const LongPath& lp) {
    int n = lp.n; vector<int> f(n), ans(n);                  // v's array: f[pos[v] + j], j < len[v]
    for (int i = n - 1; i >= 0; i--) {
        int v = lp.order[i], b = lp.pos[v];
        f[b] = 1; ans[v] = 0;
        if (lp.heavy[v] >= 0 && f[b + 1 + ans[lp.heavy[v]]] > 1) ans[v] = ans[lp.heavy[v]] + 1;   // inherited for free
        for (int c : lp.adj[v]) if (c != lp.parent[v] && c != lp.heavy[v])
            for (int j = 0; j < lp.len[c]; j++) {
                int d = j + 1; f[b + d] += f[lp.pos[c] + j];
                if (f[b + d] > f[b + ans[v]] || (f[b + d] == f[b + ans[v]] && d < ans[v])) ans[v] = d;
            }
    }
    return ans;
}

Typical uses: any DP indexed by depth below a vertex (“number of vertices at distance $k$ in the subtree”, counting triples at equal distance, $k$-th ancestor ladders in LCA) — CF 1009F and POI 2014 “Hotel” are the classic showcases. Answers about $v$ must be read while $v$ is processed, because its array is then reused by its parent. For DP indexed by value rather than depth, this layout doesn’t apply — use segment tree merging or small-to-large / DSU on tree instead.

Two-way DP: when a second array flows the other direction ($g[\text{child}][j]$ feeding $g[\text{parent}][j-1]$, as in POI “Hotel”), give each long path $2\cdot \text{len}$ cells instead of $\text{len}$ and let the “child” pointer be the parent’s pointer minus one — the same preorder layout supports both directions at once, still $O(n)$ total.

Proof: long-path inheritance is $O(n)$

pos is a preorder in which the deepest child follows its parent, so the long path through $v$ occupies consecutive cells and the array of the deepest child $h$ starts at ${\text{pos}}_v+1$: entry $j$ of $h$ is entry $j+1$ of $v$, which is exactly the shift a depth-indexed DP needs, at no cost. A light child $c$ is merged in $O({\text{len}}_c)$; $c$ is the top of its long path, whose length is ${\text{len}}_c$, and long paths partition the vertices, so the total merging cost is $\le n$. $v$’s array has ${\text{len}}_v$ cells, which fit before the next path starts because $v$‘s long path has exactly ${\text{len}}_v$ vertices from $v$ down. Dominant index: after inheriting, the best inherited depth is ${\text{ans}}_h+1$, compared with depth 0 (value 1, preferred on ties); a light merge only increases cells $\mathrm{1..}{\text{len}}_c$, each compared at its final value for that merge, so the maximum (with the smallest index on ties) is maintained.