On this page

Heavy-Light & Centroid Decomposition

The previous lesson turned subtrees into array ranges (Euler tour) and answered static path questions with LCA and prefix sums. Two harder kinds of tree problem remain. The first is dynamic paths: "set the value of node " interleaved with "maximum value on the path from to ". Prefix sums cannot handle a non-invertible aggregate like max with updates, and the subtree trick does not apply to paths. The second is all-paths questions: "how many pairs of nodes are at distance exactly ?", "which marked node is nearest to ?". There are paths, and we want near-linear time.

Heavy-light decomposition (HLD) solves the first. It cuts the tree into vertex-disjoint vertical chains such that any root-ward path crosses only of them, and lays every chain out contiguously in one array. A path query becomes range queries on a segment tree, for total, and subtree queries come for free with the same positions.

Centroid decomposition solves the second. A centroid is a node whose removal leaves no component bigger than half the tree. Remove it, recurse into the pieces, and every path in the tree passes through exactly one centroid at the highest level where its endpoints are separated. The recursion is only levels deep, so "handle all paths through the centroid" in linear time per level gives overall.

The lesson closes with small-to-large merging (DSU on tree, "sack"), a third divide-by-size technique with the same logarithmic argument, and a decision table for when to use HLD, centroid decomposition, Euler tours or binary lifting.

Why this exists

The heavy-path idea comes from Sleator and Tarjan's 1983 paper on dynamic trees (link-cut trees), where every node marks the child with the largest subtree as "heavy" and the key lemma is that a root path contains at most light edges. Harel and Tarjan used the same decomposition in their 1984 LCA algorithm. In competitive programming the static version — "heavy-light decomposition with a segment tree over the chains" — became the standard tool for path queries with updates in the late 2000s; it is less elegant than link-cut trees but far easier to write correctly, and with small constants is fast enough for .

Centroids are older still: Camille Jordan proved in 1869 that every tree has either one centroid or two adjacent ones. Using them as recursive separators is the tree case of the separator theorems that drive divide and conquer on graphs (Lipton and Tarjan's planar separator theorem, 1979, is the famous generalisation). Centroid decomposition gives an -depth hierarchy over any tree regardless of its shape — a path of nodes and a star both get a balanced centroid tree — which is why it appears in distance labelling schemes and distance oracles as well as in contest problems.

Small-to-large is the argument behind union-by-size in the disjoint-set union structure and behind Hopcroft's DFA-minimisation algorithm ("process the smaller half"): if you always move the elements of the smaller collection into the larger, each element moves at most times, because the collection it lives in at least doubles each time.

Pattern triggers

If the problem says or has…Think of…
"update a node (or edge), then max / sum / min on the path –"Heavy-light decomposition + segment tree
"add to every node on the path –" interleaved with path or subtree queriesHLD + lazy segment tree
both subtree updates/queries and path updates/queriesHLD (positions are also Euler-tour positions)
"count pairs at distance exactly " / "at most ", "paths with weight sum "Centroid decomposition
"nearest marked / red node to " with marking updatesCentroid decomposition with a per-centroid best
"for each node, the number of nodes within distance "Centroid decomposition (+ sorted lists or Fenwick trees per centroid)
"assign ranks so that two equal ranks always have a higher rank between them"The centroid tree's levels (Ciel the Commander)
"for each subtree, the number of distinct colours / the most frequent colour"Small-to-large merging, or DSU on tree (sack)
static path aggregates onlyBinary lifting or prefix sums (previous lesson) — HLD is overkill
subtree queries onlyEuler tour + Fenwick (previous lesson)
links and cuts change the tree shapeLink-cut trees or Euler-tour trees (beyond this lesson)

The literal signals: path + update, number of pairs / paths, distance exactly / at most , nearest, per subtree distinct, with around –.

Intuition & first principles

Why chains help

If the tree were a single path, path queries would be array range queries: one segment tree, each. A general tree is a bundle of paths. Choose for each node one child to "continue" its chain; the other children start new chains. A root-ward path then walks along a chain, jumps to a new chain at its top, walks along that, and so on. Each piece of walk along a chain is one contiguous range if every chain is laid out contiguously in an array. The cost of a path query is (number of chain switches + 1) range queries.

Which child should continue the chain? An arbitrary choice can be terrible: on a "caterpillar" where every node has one long arm and one short arm, choosing the short arm makes a long path switch chains at every step. Choose instead the child with the largest subtree, the heavy child; the edge to it is heavy and every other child edge is light.

Light-edge lemma. If is a light edge then . Proof: 's heavy child has , and . So climbing a light edge more than doubles the subtree size, and since sizes never exceed , any root-ward path contains at most light edges. A chain switch happens only on a light edge, so any path (which is two root-ward paths up to the LCA) touches at most chains.

Why centroids help

For "count all pairs at distance ", divide and conquer suggests: pick a node , count the paths that pass through , delete , recurse on each remaining component. Every path is counted exactly once — at the first chosen node that lies on it. The question is the depth of the recursion. Picking an endpoint of a path graph gives depth , and total work . Picking a node whose removal leaves pieces of size at most half guarantees the component containing any node halves at each level, so the depth is at most . If each level does work in total (each node belongs to one component per level), the whole algorithm is .

Why smaller-into-larger helps

To compute, for every node, a set summarising its subtree (its distinct colours), the naive approach copies each child's set into the parent: on a path. Instead, let the parent inherit its largest child's set and insert only the elements of the smaller ones. An element is inserted only when its set is merged into one at least as large, so the size of the set containing it at least doubles each time: at most insertions per element, in total (times the cost of one insertion).

Mechanics

Heavy-light decomposition

Running example (the same tree as in LCA, Binary Lifting & Euler Tour; node values in brackets). Thick arrows are heavy edges; each maximal run of thick arrows is a chain.

flowchart TD
    n0["0 [3] size 12"] ==> n1["1 [1] size 6"]
    n0 --> n2["2 [4] size 5"]
    n1 ==> n3["3 [1] size 3"]
    n1 --> n4["4 [5] size 2"]
    n3 ==> n5["5 [9] size 2"]
    n5 ==> n6["6 [2] size 1"]
    n4 ==> n11["11 [8] size 1"]
    n2 ==> n7["7 [6] size 4"]
    n7 ==> n8["8 [5] size 3"]
    n8 ==> n9["9 [3] size 2"]
    n9 ==> n10["10 [5] size 1"]

Step 1: sizes and heavy children. One BFS (or DFS) gives parents and depths; processing nodes in reverse BFS order accumulates subtree sizes; each node's heavy child is the child of maximum size (ties broken arbitrarily).

Step 2: chains and positions. A DFS that always visits the heavy child first assigns positions in visiting order. Each node's head is the top of its chain: itself if it is a light child (or the root), else its parent's head. Because the heavy child is visited immediately after its parent, every chain occupies consecutive positions; because it is a DFS, every subtree also occupies consecutive positions .

Computed by script on the example:

node01234567891011
size1265322143211
heavy child1375116–8910––
head002040022224
pos01725348910116
light edges to root001010011111

Three chains: at positions 0..4, at 5..6, at 7..11. (On this tree the heavy-first order happens to coincide with the plain DFS order of the previous lesson, because every heavy child is also the smallest-numbered child; in general they differ.) The segment tree is built over the array of values in position order: [3, 1, 1, 9, 2, 5, 8, 4, 6, 5, 3, 5].

Step 3: a path query. While and are on different chains, take the one whose chain head is deeper, query the range from its head to it, and jump to the parent of its head. When they share a chain, query the range between them. The "deeper head" rule guarantees that we never jump past the LCA: the chain with the deeper head cannot contain the LCA unless both nodes are already on it.

flowchart TD
    S["query(u, v)"] --> C{"head[u] == head[v]?"}
    C -->|"no"| D{"head of u shallower than head of v?"}
    D -->|"yes"| SW["swap u, v"]
    D -->|"no"| Q
    SW --> Q["combine segtree range from pos of head(u) to pos of u"]
    Q --> J["u = parent of head(u)"]
    J --> C
    C -->|"yes"| F["combine range between pos[u] and pos[v]"]
    F --> R["return the combined answer"]

Trace: path sum and max from 11 to 10 (computed by script):

stepuvhead[u], head[v]actionrangevalues in rangerunning sumrunning max
111104 (depth 2), 2 (depth 1)head of u deeper: take chain piece , jump to parent(4) = 15..65, 8138
21100 (depth 0), 2 (depth 1)head of v deeper: swap, take , jump to parent(2) = 07..114, 6, 5, 3, 5368
3010, 0same chain: take 0..13, 1408

Result: sum 40, max 8, from three range queries. The path is 11, 4, 1, 0, 2, 7, 8, 9, 10 and indeed . Other paths: uses two ranges (7..11 and 0..4): sum 39, max 9; is on one chain (range 8..10): sum 14, max 6.

Updates. A point update to node is a point update at . A path update ("add on ") decomposes into the same ranges, each a lazy range update. A subtree query or update on is the single range : in the example, subtree(1) is positions 1..6, sum 26.

Edge values. If values live on edges, store each edge's value at its child endpoint. A path query then excludes the LCA's position: in the final same-chain step, query where is the shallower node (and skip it if empty).

Non-commutative aggregates. When the combination order matters (string hashes along the path, matrix products, "maximum subarray on the path"), collect the pieces from the side and the side separately, reverse the -side pieces, and combine in path order. Sum and max do not care.

Centroid decomposition

Finding a centroid. Root the component anywhere, compute subtree sizes, and walk from the root: while some child has size greater than half the component, move into that child. The node where you stop is a centroid.

Building the centroid tree. Find the centroid of the whole tree, mark it removed, and recursively decompose each remaining component; the centroids of those components become 's children in the centroid tree. Computed by script on the example (component entered from the listed start node):

levelstartcomponent sizecentroidwhy it stops there
00120children of 0 have sizes 6 and 5, neither exceeds 12 / 2
1161children of 1 (rooted at 1) have sizes 3 and 2, neither exceeds 3
1258from 2: child 7 has size 4 > 2.5, move; 8 has 3 > 2.5, move; at 8 the child 9 has size 2
2335from 3: child 5 has size 2 > 1.5, move; at 5 the child 6 has size 1
2424child 11 has size 1, not more than 1
2727child 2 has size 1
2929child 10 has size 1
33, 6, 11, 2, 101 eachthemselvessingle nodes
flowchart TD
    c0["0 (level 0)"] --> c1["1 (level 1)"]
    c0 --> c8["8 (level 1)"]
    c1 --> c5["5 (level 2)"]
    c1 --> c4["4 (level 2)"]
    c5 --> c3["3 (level 3)"]
    c5 --> c6["6 (level 3)"]
    c4 --> c11["11 (level 3)"]
    c8 --> c7["7 (level 2)"]
    c8 --> c9["9 (level 2)"]
    c7 --> c2["2 (level 3)"]
    c9 --> c10["10 (level 3)"]

The centroid tree has depth 3 , even though the original tree has depth 5 and contains a path of 10 nodes. Note that the centroid tree is not a subgraph of the original tree (5 is the centroid-parent of 3 and 6, but 1 is the centroid-parent of 5 and 4 is not adjacent to 5). Its key property: for any two nodes and , their LCA in the centroid tree lies on the path between them in the original tree. That is what lets "all paths" problems be decomposed over centroid ancestors.

Counting paths of length through a centroid. At centroid , keep cnt[d] = number of already-processed nodes at distance from , starting with cnt[0] = 1 for itself. Process the subtrees of one at a time: first, for each node at depth in the current subtree, add cnt[k - d] to the answer (pairs with an endpoint in an earlier subtree or at ); then add the subtree's depths into cnt. Processing one subtree completely before inserting it prevents pairing two nodes of the same subtree, whose path does not pass through .

Trace: paths of length 3 through the top centroid 0 (computed by script):

stepsubtreedepths of its nodesmatches found (cnt[3 - d] per node)contributedcnt after inserting
start–––0{0: 1}
1via 1: nodes 1, 3, 4, 5, 11, 61, 2, 2, 3, 3, 4nodes 5 and 11 at depth 3 pair with 2{0: 1, 1: 1, 2: 2, 3: 2, 4: 1}
2via 2: nodes 2, 7, 8, 9, 101, 2, 3, 4, 5depth 1 × cnt[2] = 2, depth 2 × cnt[1] = 1, depth 3 × cnt[0] = 14–

Six paths of length 3 pass through 0. Recursing finds 3 more in the component (6–1, 5–4, 3–11) and 2 in the path –––– (2–9, 7–10), for a total of 11, matching brute force over all 66 pairs.

Nearest marked node (Codeforces 342E, Xenia and Tree). Store, for every centroid , best[c] = distance from to the nearest marked node in 's component. For every node, precompute its distance to each of its centroid ancestors (one BFS per centroid inside its component: per level, total).

  • Mark : for each centroid ancestor of (including itself), best[c] = min(best[c], dist(v, c)).
  • Query : answer over the centroid ancestors of .

Why it is correct: let be the nearest marked node, and let be the LCA of and in the centroid tree. Then is a centroid ancestor of both and lies on the – path, so ; conversely every term is the length of some walk from to a marked node, hence at least the true distance. Both operations are .

On the example with node 0 initially marked: query(10) = 5; mark 6; query(10) = 5, query(5) = 1; mark 9; query(10) = 1, query(2) = 1, query(11) = 3.

Small-to-large merging and DSU on tree

Small-to-large (explicit sets). Process nodes bottom-up. Each node takes over the set of its largest child (by set size or subtree size), inserts the elements of the other children's sets and its own colour, and records the size. Swapping set references makes the "take over" free. set insertions, with balanced trees or expected with hash sets.

DSU on tree / sack (implicit, one global counter). Using the Euler-tour positions so that each subtree is a range:

  1. For node , first solve all light children, each time clearing the global counter afterwards.
  2. Solve the heavy child and keep its contributions in the counter.
  3. Add and every node of its light subtrees (iterate their position ranges) to the counter; now the counter describes 's subtree. Answer 's query.
  4. If is itself a light child, clear everything it added.

A node is re-added once for each light edge above it, at most times, so the total is counter operations. This is the technique behind Codeforces 600E "Lomsat gelral" (the most frequent colour in every subtree). It is the same heavy/light idea as HLD, used for a completely different purpose.

The ladder: brute force → better → optimal

Ladder 1: path maximum with point updates

Rung 0: walk the path, per query. Climb from both ends to the LCA and take the max. Updates are . on a path-shaped tree: steps.

Rung 1: binary lifting with a max table, query, update. Static path max is with , but an update to changes every jump entry passing over — up to of them on a path.

Rung 2: sqrt decomposition on the tree. Group nodes into blocks of depth and store, for each node, the max up to its block's top: per query and per update. Rarely worth the complexity.

Rung 3: heavy-light decomposition + segment tree, query, update. At most chain pieces, each an segment-tree query. In practice much better than the bound: most paths cross few light edges, and the pieces near the root are short.

Rung 4: link-cut trees, amortised for everything, including changing the tree (link and cut). Much harder to implement; reserved for dynamic forests.

RungQueryUpdateCode sizeHandles link/cut
walk the pathtinyyes
binary lifting max worstsmallno
tree sqrt decompositionmediumno
HLD + segment treemediumno
link-cut tree amortised amortisedlargeyes

Ladder 2: count pairs at distance exactly

Rung 0: BFS from every node, . Count pairs at distance from each source, halve. gives .

Rung 1: tree DP, . dp[v][d] = number of nodes in 's subtree at depth below ; merge children pairing depths (for nodes in different child subtrees) — Codeforces 161D's intended solution with . Fails when can be .

Rung 2: centroid decomposition, . Each level costs with an array cnt sized by the component's depth (clear only what you touched). Works for any and generalises to "at most " with a Fenwick tree ().

Rung 3: small-to-large / long-path decomposition on depth arrays, or . Merging depth-count arrays by inheriting the deepest child's array (long-path decomposition) gives for some depth-indexed problems such as Codeforces 1009F. Elegant but problem-specific.

RungTimeWorks for any Generalises to "at most "
BFS from every nodeyesyes
tree DP on depthsnoyes
centroid decompositionyesyes,
long-path merging for some variantsyesdepends

Correctness

HLD: chain count

Lemma (light edges). Every root-to-node path has at most light edges.

Proof. Let the light edges on the path, from the bottom up, enter nodes from children . By the light-edge inequality , and is an ancestor of (or equal to it), so . With this gives , and since , .

The path between and is the union of two root-ward paths ending at the LCA, so it meets at most chains.

HLD: contiguity and the query loop

Contiguity. In a DFS that visits the heavy child first, the heavy child of receives position ; by induction down the chain, a chain occupies positions . Every subtree is contiguous because it is a DFS (the argument of the previous lesson).

Query loop. Invariant: the answer accumulated so far covers exactly the nodes of the original path that are not on the current path from to , and the current and are on the original path (or are its endpoints moved toward the LCA). Suppose and . Then is not an ancestor of : if it were, would lie in 's subtree, and since is not on 's chain, the path from up to would enter the chain through a light edge at a node of depth at least , putting strictly deeper than — a contradiction. So the whole chain segment from to lies strictly below the LCA on 's side of the path, and replacing by removes exactly those nodes from the current path. When the heads coincide, and are on one chain, one is an ancestor of the other, and the remaining path is the range between their positions. Each iteration crosses a light edge, so by the lemma there are iterations.

Centroids: existence and the walk

Theorem (Jordan, 1869). Every tree with nodes has a node whose removal leaves components of size at most .

Proof (via the walk). Root the tree at and start at . If some child of has , move to it. This can happen at most once per level and sizes strictly decrease, so the walk stops at some node . At that point every child component of has size at most . The remaining component — everything outside 's subtree — has size . If it is empty. Otherwise we moved into because , so . All components are at most .

(If is even and some edge splits the tree into two halves of exactly , both endpoints are centroids; in the example, 0 and 1 are both centroids because removing the edge 0–1 leaves two components of 6 nodes. Otherwise the centroid is unique.)

Centroid tree depth

Lemma. The centroid tree has depth at most .

Proof. A component at level has size at most , because each recursion step enters a component of size at most half the previous one. A component has at least one node, so , giving .

Each path is handled exactly once. For any path between and , consider the first centroid (in recursion order) that lies on . Before it was removed, all of was inside one component (no node of had been removed, so 's nodes were connected); that component's centroid is on , and after its removal and are in different components or one of them is the centroid. So is counted at exactly that centroid and never again. With the "process one subtree, then insert it" order, pairs inside the same child subtree are never paired at this centroid. Summing over centroids counts every path exactly once.

Small-to-large

Each time an element is inserted into a set, it comes from a set no larger than the destination (the destination is the largest child's set). The resulting set has at least twice the size of the element's previous set. Set sizes never exceed , so each element is inserted at most times: insertions. For DSU on tree, a node is re-added once per light edge on its root path, at most times by the light-edge lemma.

Complexity

TechniquePreprocessingPer operationMemory
HLD path query (sum, max) + segment tree build
HLD point update––
HLD path update (lazy)––
HLD subtree query/update––
HLD LCA (by itself)
centroid decomposition build–
+ distances to centroid ancestors–
nearest marked node––
count paths of length total–
small-to-large (hash sets) expected–
DSU on tree–

Constants. HLD's bound is rarely tight. On random trees the number of light edges on a path is small, and a common optimisation is to use a segment tree query only for chain pieces and an prefix array when the chain piece starts at the chain head and the operation is invertible. HLD is also a decent LCA algorithm on its own ( preprocessing, query, tiny memory, cache-friendly because chain jumps are few). Centroid decomposition's cost is dominated by the per-level BFS/DFS over components; iterative implementations avoid Python recursion limits and the overhead of deep recursion in C++ and Java. Memory for per-node centroid-ancestor distances is — 3.6 million integers for .

Implementation

Two code groups with the same tests in all four languages, on the 12-node example tree.

  1. HLD: sizes, heavy children, heads and positions (iterative), an iterative segment tree storing sum and max, pathSum, pathMax, subtreeSum and set (assign a node's value).
  2. CentroidXenia: iterative centroid decomposition, distances to centroid ancestors, paint(v) and query(v) for the nearest painted node; tests check the centroid-tree parent array and a sequence of operations.
from collections import deque

NEG = float("-inf")


class HLD:
    def __init__(self, n: int, edges: list[tuple[int, int]], values: list[int], root: int = 0):
        adj: list[list[int]] = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        for nb in adj:
            nb.sort()
        self.n = n
        self.parent, self.depth, order = [-1] * n, [0] * n, []
        seen = [False] * n
        seen[root] = True
        q = deque([root])
        while q:                                       # BFS: parent, depth, order
            x = q.popleft()
            order.append(x)
            for y in adj[x]:
                if not seen[y]:
                    seen[y] = True
                    self.parent[y], self.depth[y] = x, self.depth[x] + 1
                    q.append(y)
        self.size = [1] * n
        for x in reversed(order):
            if self.parent[x] >= 0:
                self.size[self.parent[x]] += self.size[x]
        self.heavy = [-1] * n
        for x in range(n):
            best = 0
            for y in adj[x]:
                if y != self.parent[x] and self.size[y] > best:
                    best, self.heavy[x] = self.size[y], y
        self.head, self.pos = [0] * n, [0] * n
        cur, stack = 0, [root]
        while stack:                                   # DFS, heavy child visited first
            x = stack.pop()
            p = self.parent[x]
            self.head[x] = self.head[p] if p >= 0 and self.heavy[p] == x else x
            self.pos[x] = cur
            cur += 1
            for y in adj[x]:
                if y != p and y != self.heavy[x]:
                    stack.append(y)
            if self.heavy[x] != -1:
                stack.append(self.heavy[x])            # pushed last, popped next
        self.sm = [0] * (2 * n)                        # iterative segment tree: sum and max
        self.mx = [NEG] * (2 * n)
        for v in range(n):
            self.sm[n + self.pos[v]] = self.mx[n + self.pos[v]] = values[v]
        for i in range(n - 1, 0, -1):
            self.sm[i] = self.sm[2 * i] + self.sm[2 * i + 1]
            self.mx[i] = max(self.mx[2 * i], self.mx[2 * i + 1])

    def set(self, v: int, value: int) -> None:
        i = self.pos[v] + self.n
        self.sm[i] = self.mx[i] = value
        i //= 2
        while i:
            self.sm[i] = self.sm[2 * i] + self.sm[2 * i + 1]
            self.mx[i] = max(self.mx[2 * i], self.mx[2 * i + 1])
            i //= 2

    def _range(self, l: int, r: int) -> tuple[int, int]:   # inclusive positions
        s, m = 0, NEG
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                s, m = s + self.sm[l], max(m, self.mx[l])
                l += 1
            if r & 1:
                r -= 1
                s, m = s + self.sm[r], max(m, self.mx[r])
            l //= 2
            r //= 2
        return s, m

    def _path(self, u: int, v: int) -> tuple[int, int]:
        s, m = 0, NEG
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] < self.depth[self.head[v]]:
                u, v = v, u
            ps, pm = self._range(self.pos[self.head[u]], self.pos[u])
            s, m = s + ps, max(m, pm)
            u = self.parent[self.head[u]]
        lo, hi = sorted((self.pos[u], self.pos[v]))
        ps, pm = self._range(lo, hi)
        return s + ps, max(m, pm)

    def path_sum(self, u: int, v: int) -> int:
        return self._path(u, v)[0]

    def path_max(self, u: int, v: int) -> int:
        return self._path(u, v)[1]

    def subtree_sum(self, v: int) -> int:
        return self._range(self.pos[v], self.pos[v] + self.size[v] - 1)[0]


if __name__ == "__main__":
    edges = [(0, 1), (0, 2), (1, 3), (1, 4), (3, 5), (5, 6), (2, 7), (7, 8), (8, 9), (9, 10), (4, 11)]
    h = HLD(12, edges, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8])
    assert h.head == [0, 0, 2, 0, 4, 0, 0, 2, 2, 2, 2, 4]
    assert h.pos == [0, 1, 7, 2, 5, 3, 4, 8, 9, 10, 11, 6]
    assert [h.path_sum(10, 6), h.path_sum(6, 11), h.path_sum(9, 7), h.path_sum(11, 10)] == [39, 26, 14, 40]
    assert [h.path_max(10, 6), h.path_max(6, 11), h.path_max(9, 7), h.path_max(11, 10)] == [9, 9, 6, 8]
    assert [h.subtree_sum(v) for v in range(12)] == [52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8]
    h.set(3, 11)
    assert h.path_sum(10, 6) == 49 and h.path_max(10, 6) == 11 and h.subtree_sum(1) == 36
    assert h.path_max(9, 7) == 6 and h.path_sum(11, 10) == 40
    print("all tests pass")
import java.util.*;

public class HLD {
    final int n;
    final int[] parent, depth, size, heavy, head, pos;
    final long[] sm, mx;
    static final long NEG = Long.MIN_VALUE;

    HLD(int n, int[][] edges, int[] values, int root) {
        this.n = n;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        for (List<Integer> nb : adj) Collections.sort(nb);
        parent = new int[n]; depth = new int[n]; size = new int[n]; heavy = new int[n]; head = new int[n]; pos = new int[n];
        Arrays.fill(parent, -1);
        int[] order = new int[n];
        boolean[] seen = new boolean[n];
        int qh = 0, qt = 0;
        order[qt++] = root; seen[root] = true;
        while (qh < qt) {
            int x = order[qh++];
            for (int y : adj.get(x)) if (!seen[y]) { seen[y] = true; parent[y] = x; depth[y] = depth[x] + 1; order[qt++] = y; }
        }
        Arrays.fill(size, 1);
        for (int i = n - 1; i >= 0; i--) if (parent[order[i]] >= 0) size[parent[order[i]]] += size[order[i]];
        Arrays.fill(heavy, -1);
        for (int x = 0; x < n; x++) {
            int best = 0;
            for (int y : adj.get(x)) if (y != parent[x] && size[y] > best) { best = size[y]; heavy[x] = y; }
        }
        int cur = 0;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            int x = stack.pop(), p = parent[x];
            head[x] = (p >= 0 && heavy[p] == x) ? head[p] : x;
            pos[x] = cur++;
            for (int y : adj.get(x)) if (y != p && y != heavy[x]) stack.push(y);
            if (heavy[x] != -1) stack.push(heavy[x]);
        }
        sm = new long[2 * n];
        mx = new long[2 * n];
        Arrays.fill(mx, NEG);
        for (int v = 0; v < n; v++) { sm[n + pos[v]] = values[v]; mx[n + pos[v]] = values[v]; }
        for (int i = n - 1; i > 0; i--) { sm[i] = sm[2 * i] + sm[2 * i + 1]; mx[i] = Math.max(mx[2 * i], mx[2 * i + 1]); }
    }

    void set(int v, long value) {
        int i = pos[v] + n;
        sm[i] = value; mx[i] = value;
        for (i /= 2; i > 0; i /= 2) { sm[i] = sm[2 * i] + sm[2 * i + 1]; mx[i] = Math.max(mx[2 * i], mx[2 * i + 1]); }
    }

    long[] range(int l, int r) {
        long s = 0, m = NEG;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if ((l & 1) == 1) { s += sm[l]; m = Math.max(m, mx[l]); l++; }
            if ((r & 1) == 1) { r--; s += sm[r]; m = Math.max(m, mx[r]); }
        }
        return new long[]{s, m};
    }

    long[] path(int u, int v) {
        long s = 0, m = NEG;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) { int t = u; u = v; v = t; }
            long[] p = range(pos[head[u]], pos[u]);
            s += p[0]; m = Math.max(m, p[1]);
            u = parent[head[u]];
        }
        long[] p = range(Math.min(pos[u], pos[v]), Math.max(pos[u], pos[v]));
        return new long[]{s + p[0], Math.max(m, p[1])};
    }

    long pathSum(int u, int v) { return path(u, v)[0]; }
    long pathMax(int u, int v) { return path(u, v)[1]; }
    long subtreeSum(int v) { return range(pos[v], pos[v] + size[v] - 1)[0]; }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
        HLD h = new HLD(12, edges, new int[]{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8}, 0);
        check(Arrays.equals(h.head, new int[]{0, 0, 2, 0, 4, 0, 0, 2, 2, 2, 2, 4}), "head");
        check(Arrays.equals(h.pos, new int[]{0, 1, 7, 2, 5, 3, 4, 8, 9, 10, 11, 6}), "pos");
        check(h.pathSum(10, 6) == 39 && h.pathSum(6, 11) == 26 && h.pathSum(9, 7) == 14 && h.pathSum(11, 10) == 40, "sum");
        check(h.pathMax(10, 6) == 9 && h.pathMax(6, 11) == 9 && h.pathMax(9, 7) == 6 && h.pathMax(11, 10) == 8, "max");
        long[] subs = {52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8};
        for (int v = 0; v < 12; v++) check(h.subtreeSum(v) == subs[v], "subtree " + v);
        h.set(3, 11);
        check(h.pathSum(10, 6) == 49 && h.pathMax(10, 6) == 11 && h.subtreeSum(1) == 36, "after set");
        check(h.pathMax(9, 7) == 6 && h.pathSum(11, 10) == 40, "unaffected");
        System.out.println("all tests pass");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

struct HLD {
    int n;
    std::vector<int> parent, depth, size, heavy, head, pos;
    std::vector<long long> sm, mx;
    static constexpr long long NEG = std::numeric_limits<long long>::min();

    HLD(int n_, const std::vector<std::pair<int, int>>& edges, const std::vector<int>& values, int root = 0)
        : n(n_), parent(n_, -1), depth(n_, 0), size(n_, 1), heavy(n_, -1), head(n_, 0), pos(n_, 0),
          sm(2 * n_, 0), mx(2 * n_, NEG) {
        std::vector<std::vector<int>> adj(n);
        for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
        for (auto& nb : adj) std::sort(nb.begin(), nb.end());
        std::vector<int> order{root};
        std::vector<bool> seen(n, false);
        seen[root] = true;
        for (std::size_t i = 0; i < order.size(); ++i) {
            int x = order[i];
            for (int y : adj[x]) if (!seen[y]) { seen[y] = true; parent[y] = x; depth[y] = depth[x] + 1; order.push_back(y); }
        }
        for (int i = n - 1; i >= 0; --i) if (parent[order[i]] >= 0) size[parent[order[i]]] += size[order[i]];
        for (int x = 0; x < n; ++x) {
            int best = 0;
            for (int y : adj[x]) if (y != parent[x] && size[y] > best) { best = size[y]; heavy[x] = y; }
        }
        int cur = 0;
        std::vector<int> stack{root};
        while (!stack.empty()) {
            int x = stack.back(); stack.pop_back();
            int p = parent[x];
            head[x] = (p >= 0 && heavy[p] == x) ? head[p] : x;
            pos[x] = cur++;
            for (int y : adj[x]) if (y != p && y != heavy[x]) stack.push_back(y);
            if (heavy[x] != -1) stack.push_back(heavy[x]);
        }
        for (int v = 0; v < n; ++v) sm[n + pos[v]] = mx[n + pos[v]] = values[v];
        for (int i = n - 1; i > 0; --i) { sm[i] = sm[2 * i] + sm[2 * i + 1]; mx[i] = std::max(mx[2 * i], mx[2 * i + 1]); }
    }

    void set(int v, long long value) {
        int i = pos[v] + n;
        sm[i] = mx[i] = value;
        for (i /= 2; i > 0; i /= 2) { sm[i] = sm[2 * i] + sm[2 * i + 1]; mx[i] = std::max(mx[2 * i], mx[2 * i + 1]); }
    }

    std::pair<long long, long long> range(int l, int r) const {
        long long s = 0, m = NEG;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) { s += sm[l]; m = std::max(m, mx[l]); ++l; }
            if (r & 1) { --r; s += sm[r]; m = std::max(m, mx[r]); }
        }
        return {s, m};
    }

    std::pair<long long, long long> path(int u, int v) const {
        long long s = 0, m = NEG;
        while (head[u] != head[v]) {
            if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
            auto [ps, pm] = range(pos[head[u]], pos[u]);
            s += ps; m = std::max(m, pm);
            u = parent[head[u]];
        }
        auto [ps, pm] = range(std::min(pos[u], pos[v]), std::max(pos[u], pos[v]));
        return {s + ps, std::max(m, pm)};
    }

    long long pathSum(int u, int v) const { return path(u, v).first; }
    long long pathMax(int u, int v) const { return path(u, v).second; }
    long long subtreeSum(int v) const { return range(pos[v], pos[v] + size[v] - 1).first; }
};

int main() {
    std::vector<std::pair<int, int>> edges{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
    HLD h(12, edges, {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8});
    assert((h.head == std::vector<int>{0, 0, 2, 0, 4, 0, 0, 2, 2, 2, 2, 4}));
    assert((h.pos == std::vector<int>{0, 1, 7, 2, 5, 3, 4, 8, 9, 10, 11, 6}));
    assert(h.pathSum(10, 6) == 39 && h.pathSum(6, 11) == 26 && h.pathSum(9, 7) == 14 && h.pathSum(11, 10) == 40);
    assert(h.pathMax(10, 6) == 9 && h.pathMax(6, 11) == 9 && h.pathMax(9, 7) == 6 && h.pathMax(11, 10) == 8);
    std::vector<long long> subs{52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8};
    for (int v = 0; v < 12; ++v) assert(h.subtreeSum(v) == subs[v]);
    h.set(3, 11);
    assert(h.pathSum(10, 6) == 49 && h.pathMax(10, 6) == 11 && h.subtreeSum(1) == 36);
    assert(h.pathMax(9, 7) == 6 && h.pathSum(11, 10) == 40);
    std::cout << "all tests pass\n";
}
class HLD {
  n: number;
  parent: number[];
  depth: number[];
  size: number[];
  heavy: number[];
  head: number[];
  pos: number[];
  sm: number[];
  mx: number[];

  constructor(n: number, edges: [number, number][], values: number[], root = 0) {
    this.n = n;
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
    for (const nb of adj) nb.sort((x, y) => x - y);
    this.parent = new Array<number>(n).fill(-1);
    this.depth = new Array<number>(n).fill(0);
    const order = [root], seen = new Array<boolean>(n).fill(false);
    seen[root] = true;
    for (let i = 0; i < order.length; i++) {
      const x = order[i];
      for (const y of adj[x]) if (!seen[y]) { seen[y] = true; this.parent[y] = x; this.depth[y] = this.depth[x] + 1; order.push(y); }
    }
    this.size = new Array<number>(n).fill(1);
    for (let i = n - 1; i >= 0; i--) if (this.parent[order[i]] >= 0) this.size[this.parent[order[i]]] += this.size[order[i]];
    this.heavy = new Array<number>(n).fill(-1);
    for (let x = 0; x < n; x++) {
      let best = 0;
      for (const y of adj[x]) if (y !== this.parent[x] && this.size[y] > best) { best = this.size[y]; this.heavy[x] = y; }
    }
    this.head = new Array<number>(n).fill(0);
    this.pos = new Array<number>(n).fill(0);
    let cur = 0;
    const stack = [root];
    while (stack.length > 0) {
      const x = stack.pop() as number, p = this.parent[x];
      this.head[x] = p >= 0 && this.heavy[p] === x ? this.head[p] : x;
      this.pos[x] = cur++;
      for (const y of adj[x]) if (y !== p && y !== this.heavy[x]) stack.push(y);
      if (this.heavy[x] !== -1) stack.push(this.heavy[x]);
    }
    this.sm = new Array<number>(2 * n).fill(0);
    this.mx = new Array<number>(2 * n).fill(-Infinity);
    for (let v = 0; v < n; v++) { this.sm[n + this.pos[v]] = values[v]; this.mx[n + this.pos[v]] = values[v]; }
    for (let i = n - 1; i > 0; i--) { this.sm[i] = this.sm[2 * i] + this.sm[2 * i + 1]; this.mx[i] = Math.max(this.mx[2 * i], this.mx[2 * i + 1]); }
  }

  set(v: number, value: number): void {
    let i = this.pos[v] + this.n;
    this.sm[i] = value; this.mx[i] = value;
    for (i = i >> 1; i > 0; i >>= 1) { this.sm[i] = this.sm[2 * i] + this.sm[2 * i + 1]; this.mx[i] = Math.max(this.mx[2 * i], this.mx[2 * i + 1]); }
  }

  range(l: number, r: number): [number, number] {
    let s = 0, m = -Infinity;
    for (l += this.n, r += this.n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) { s += this.sm[l]; m = Math.max(m, this.mx[l]); l++; }
      if (r & 1) { r--; s += this.sm[r]; m = Math.max(m, this.mx[r]); }
    }
    return [s, m];
  }

  path(u: number, v: number): [number, number] {
    let s = 0, m = -Infinity;
    while (this.head[u] !== this.head[v]) {
      if (this.depth[this.head[u]] < this.depth[this.head[v]]) [u, v] = [v, u];
      const [ps, pm] = this.range(this.pos[this.head[u]], this.pos[u]);
      s += ps; m = Math.max(m, pm);
      u = this.parent[this.head[u]];
    }
    const [ps, pm] = this.range(Math.min(this.pos[u], this.pos[v]), Math.max(this.pos[u], this.pos[v]));
    return [s + ps, Math.max(m, pm)];
  }

  pathSum(u: number, v: number): number { return this.path(u, v)[0]; }
  pathMax(u: number, v: number): number { return this.path(u, v)[1]; }
  subtreeSum(v: number): number { return this.range(this.pos[v], this.pos[v] + this.size[v] - 1)[0]; }
}

function assert(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }

const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 5], [5, 6], [2, 7], [7, 8], [8, 9], [9, 10], [4, 11]];
const h = new HLD(12, edges, [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8]);
assert(h.head.join(",") === "0,0,2,0,4,0,0,2,2,2,2,4", "head");
assert(h.pos.join(",") === "0,1,7,2,5,3,4,8,9,10,11,6", "pos");
assert(h.pathSum(10, 6) === 39 && h.pathSum(6, 11) === 26 && h.pathSum(9, 7) === 14 && h.pathSum(11, 10) === 40, "sum");
assert(h.pathMax(10, 6) === 9 && h.pathMax(6, 11) === 9 && h.pathMax(9, 7) === 6 && h.pathMax(11, 10) === 8, "max");
const subs = [52, 26, 23, 12, 13, 11, 2, 19, 13, 8, 5, 8];
for (let v = 0; v < 12; v++) assert(h.subtreeSum(v) === subs[v], `subtree ${v}`);
h.set(3, 11);
assert(h.pathSum(10, 6) === 49 && h.pathMax(10, 6) === 11 && h.subtreeSum(1) === 36, "after set");
assert(h.pathMax(9, 7) === 6 && h.pathSum(11, 10) === 40, "unaffected");
console.log("all tests pass");

The centroid group decomposes iteratively (an explicit stack of component start nodes), stores for each node the list of (centroid ancestor, distance) pairs from one BFS per centroid, and answers Xenia-style operations. Node 0 starts painted, as node 1 does in the original problem.

from collections import deque

INF = float("inf")


class CentroidXenia:
    def __init__(self, n: int, edges: list[tuple[int, int]]):
        self.adj: list[list[int]] = [[] for _ in range(n)]
        for a, b in edges:
            self.adj[a].append(b)
            self.adj[b].append(a)
        for nb in self.adj:
            nb.sort()
        self.removed = [False] * n
        self.cpar = [-1] * n
        self.anc: list[list[tuple[int, int]]] = [[] for _ in range(n)]   # (centroid, distance), top-down
        stack = [(0, -1)]
        while stack:
            start, parent_c = stack.pop()
            c = self._centroid(start)
            self.cpar[c] = parent_c
            self._record_distances(c)
            self.removed[c] = True
            for y in self.adj[c]:
                if not self.removed[y]:
                    stack.append((y, c))
        self.best = [INF] * n

    def _component(self, s: int) -> tuple[list[int], dict[int, int]]:
        par, order = {s: -1}, [s]
        for x in order:                                 # BFS over the current component
            for y in self.adj[x]:
                if not self.removed[y] and y != par[x]:
                    par[y] = x
                    order.append(y)
        return order, par

    def _centroid(self, s: int) -> int:
        order, par = self._component(s)
        size = {x: 1 for x in order}
        for x in reversed(order):
            if par[x] != -1:
                size[par[x]] += size[x]
        total, c = len(order), s
        while True:
            nxt = next((y for y in self.adj[c] if not self.removed[y] and y != par[c] and 2 * size[y] > total), None)
            if nxt is None:
                return c
            c = nxt

    def _record_distances(self, c: int) -> None:
        dist = {c: 0}
        q = deque([c])
        while q:
            x = q.popleft()
            self.anc[x].append((c, dist[x]))
            for y in self.adj[x]:
                if not self.removed[y] and y not in dist:
                    dist[y] = dist[x] + 1
                    q.append(y)

    def paint(self, v: int) -> None:
        for c, d in self.anc[v]:
            self.best[c] = min(self.best[c], d)

    def query(self, v: int) -> int:
        return min(self.best[c] + d for c, d in self.anc[v])


if __name__ == "__main__":
    edges = [(0, 1), (0, 2), (1, 3), (1, 4), (3, 5), (5, 6), (2, 7), (7, 8), (8, 9), (9, 10), (4, 11)]
    t = CentroidXenia(12, edges)
    assert t.cpar == [-1, 0, 7, 5, 1, 1, 5, 8, 0, 8, 9, 4]
    assert max(len(a) for a in t.anc) == 4                      # centroid depth 3 -> at most 4 ancestors
    t.paint(0)
    out = [t.query(10)]
    t.paint(6)
    out += [t.query(10), t.query(5)]
    t.paint(9)
    out += [t.query(10), t.query(2), t.query(11)]
    assert out == [5, 5, 1, 1, 1, 3]
    print("all tests pass")
import java.util.*;

public class CentroidXenia {
    final List<List<Integer>> adj = new ArrayList<>();
    final boolean[] removed;
    final int[] cpar, best;
    final List<List<int[]>> anc = new ArrayList<>();       // (centroid, distance), top-down
    static final int INF = Integer.MAX_VALUE / 2;

    CentroidXenia(int n, int[][] edges) {
        for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); anc.add(new ArrayList<>()); }
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        for (List<Integer> nb : adj) Collections.sort(nb);
        removed = new boolean[n];
        cpar = new int[n];
        best = new int[n];
        Arrays.fill(best, INF);
        int[] par = new int[n], size = new int[n], dist = new int[n];
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{0, -1});
        while (!stack.isEmpty()) {
            int[] top = stack.pop();
            int start = top[0];
            // BFS the component
            List<Integer> order = new ArrayList<>();
            order.add(start); par[start] = -1;
            for (int i = 0; i < order.size(); i++) {
                int x = order.get(i);
                for (int y : adj.get(x)) if (!removed[y] && y != par[x]) { par[y] = x; order.add(y); }
            }
            for (int x : order) size[x] = 1;
            for (int i = order.size() - 1; i > 0; i--) size[par[order.get(i)]] += size[order.get(i)];
            int total = order.size(), c = start;
            while (true) {
                int nxt = -1;
                for (int y : adj.get(c)) if (!removed[y] && y != par[c] && 2 * size[y] > total) nxt = y;
                if (nxt == -1) break;
                c = nxt;
            }
            cpar[c] = top[1];
            // distances from c inside the component
            ArrayDeque<Integer> q = new ArrayDeque<>();
            Set<Integer> seen = new HashSet<>();
            q.add(c); seen.add(c); dist[c] = 0;
            while (!q.isEmpty()) {
                int x = q.poll();
                anc.get(x).add(new int[]{c, dist[x]});
                for (int y : adj.get(x)) if (!removed[y] && seen.add(y)) { dist[y] = dist[x] + 1; q.add(y); }
            }
            removed[c] = true;
            for (int y : adj.get(c)) if (!removed[y]) stack.push(new int[]{y, c});
        }
    }

    void paint(int v) { for (int[] cd : anc.get(v)) best[cd[0]] = Math.min(best[cd[0]], cd[1]); }

    int query(int v) {
        int ans = INF;
        for (int[] cd : anc.get(v)) ans = Math.min(ans, best[cd[0]] + cd[1]);
        return ans;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
        CentroidXenia t = new CentroidXenia(12, edges);
        check(Arrays.equals(t.cpar, new int[]{-1, 0, 7, 5, 1, 1, 5, 8, 0, 8, 9, 4}), "cpar");
        int deepest = 0;
        for (List<int[]> a : t.anc) deepest = Math.max(deepest, a.size());
        check(deepest == 4, "depth");
        t.paint(0);
        int[] out = new int[6];
        out[0] = t.query(10);
        t.paint(6);
        out[1] = t.query(10); out[2] = t.query(5);
        t.paint(9);
        out[3] = t.query(10); out[4] = t.query(2); out[5] = t.query(11);
        check(Arrays.equals(out, new int[]{5, 5, 1, 1, 1, 3}), "queries");
        System.out.println("all tests pass");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

struct CentroidXenia {
    static constexpr int INF = 1 << 29;
    std::vector<std::vector<int>> adj;
    std::vector<bool> removed;
    std::vector<int> cpar, best;
    std::vector<std::vector<std::pair<int, int>>> anc;   // (centroid, distance), top-down

    CentroidXenia(int n, const std::vector<std::pair<int, int>>& edges)
        : adj(n), removed(n, false), cpar(n, -1), best(n, INF), anc(n) {
        for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
        for (auto& nb : adj) std::sort(nb.begin(), nb.end());
        std::vector<int> par(n), size(n), dist(n, -1);
        std::vector<std::pair<int, int>> stack{{0, -1}};
        while (!stack.empty()) {
            auto [start, parentC] = stack.back();
            stack.pop_back();
            std::vector<int> order{start};
            par[start] = -1;
            for (std::size_t i = 0; i < order.size(); ++i) {
                int x = order[i];
                for (int y : adj[x]) if (!removed[y] && y != par[x]) { par[y] = x; order.push_back(y); }
            }
            for (int x : order) size[x] = 1;
            for (std::size_t i = order.size() - 1; i > 0; --i) size[par[order[i]]] += size[order[i]];
            int total = static_cast<int>(order.size()), c = start;
            while (true) {
                int nxt = -1;
                for (int y : adj[c]) if (!removed[y] && y != par[c] && 2 * size[y] > total) nxt = y;
                if (nxt == -1) break;
                c = nxt;
            }
            cpar[c] = parentC;
            std::queue<int> q;
            q.push(c);
            dist[c] = 0;
            std::vector<int> touched{c};
            while (!q.empty()) {
                int x = q.front(); q.pop();
                anc[x].push_back({c, dist[x]});
                for (int y : adj[x]) if (!removed[y] && dist[y] < 0) { dist[y] = dist[x] + 1; touched.push_back(y); q.push(y); }
            }
            for (int x : touched) dist[x] = -1;
            removed[c] = true;
            for (int y : adj[c]) if (!removed[y]) stack.push_back({y, c});
        }
    }

    void paint(int v) { for (auto [c, d] : anc[v]) best[c] = std::min(best[c], d); }

    int query(int v) const {
        int ans = INF;
        for (auto [c, d] : anc[v]) ans = std::min(ans, best[c] + d);
        return ans;
    }
};

int main() {
    std::vector<std::pair<int, int>> edges{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {2, 7}, {7, 8}, {8, 9}, {9, 10}, {4, 11}};
    CentroidXenia t(12, edges);
    assert((t.cpar == std::vector<int>{-1, 0, 7, 5, 1, 1, 5, 8, 0, 8, 9, 4}));
    std::size_t deepest = 0;
    for (const auto& a : t.anc) deepest = std::max(deepest, a.size());
    assert(deepest == 4);
    t.paint(0);
    std::vector<int> out{t.query(10)};
    t.paint(6);
    out.push_back(t.query(10)); out.push_back(t.query(5));
    t.paint(9);
    out.push_back(t.query(10)); out.push_back(t.query(2)); out.push_back(t.query(11));
    assert((out == std::vector<int>{5, 5, 1, 1, 1, 3}));
    std::cout << "all tests pass\n";
}
class CentroidXenia {
  adj: number[][];
  removed: boolean[];
  cpar: number[];
  best: number[];
  anc: [number, number][][];   // (centroid, distance), top-down

  constructor(n: number, edges: [number, number][]) {
    this.adj = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) { this.adj[a].push(b); this.adj[b].push(a); }
    for (const nb of this.adj) nb.sort((x, y) => x - y);
    this.removed = new Array<boolean>(n).fill(false);
    this.cpar = new Array<number>(n).fill(-1);
    this.best = new Array<number>(n).fill(Infinity);
    this.anc = Array.from({ length: n }, () => []);
    const par = new Array<number>(n).fill(-1), size = new Array<number>(n).fill(0), dist = new Array<number>(n).fill(-1);
    const stack: [number, number][] = [[0, -1]];
    while (stack.length > 0) {
      const [start, parentC] = stack.pop() as [number, number];
      const order = [start];
      par[start] = -1;
      for (let i = 0; i < order.length; i++) {
        const x = order[i];
        for (const y of this.adj[x]) if (!this.removed[y] && y !== par[x]) { par[y] = x; order.push(y); }
      }
      for (const x of order) size[x] = 1;
      for (let i = order.length - 1; i > 0; i--) size[par[order[i]]] += size[order[i]];
      const total = order.length;
      let c = start;
      for (;;) {
        let nxt = -1;
        for (const y of this.adj[c]) if (!this.removed[y] && y !== par[c] && 2 * size[y] > total) nxt = y;
        if (nxt === -1) break;
        c = nxt;
      }
      this.cpar[c] = parentC;
      const q = [c], touched = [c];
      dist[c] = 0;
      for (let h = 0; h < q.length; h++) {
        const x = q[h];
        this.anc[x].push([c, dist[x]]);
        for (const y of this.adj[x]) if (!this.removed[y] && dist[y] < 0) { dist[y] = dist[x] + 1; touched.push(y); q.push(y); }
      }
      for (const x of touched) dist[x] = -1;
      this.removed[c] = true;
      for (const y of this.adj[c]) if (!this.removed[y]) stack.push([y, c]);
    }
  }

  paint(v: number): void { for (const [c, d] of this.anc[v]) this.best[c] = Math.min(this.best[c], d); }

  query(v: number): number {
    let ans = Infinity;
    for (const [c, d] of this.anc[v]) ans = Math.min(ans, this.best[c] + d);
    return ans;
  }
}

function assert(ok: boolean, msg: string): void { if (!ok) throw new Error(msg); }

const edges: [number, number][] = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 5], [5, 6], [2, 7], [7, 8], [8, 9], [9, 10], [4, 11]];
const t = new CentroidXenia(12, edges);
assert(t.cpar.join(",") === "-1,0,7,5,1,1,5,8,0,8,9,4", "cpar");
assert(Math.max(...t.anc.map((a) => a.length)) === 4, "depth");
t.paint(0);
const out = [t.query(10)];
t.paint(6);
out.push(t.query(10), t.query(5));
t.paint(9);
out.push(t.query(10), t.query(2), t.query(11));
assert(out.join(",") === "5,5,1,1,1,3", "queries");
console.log("all tests pass");

Real-world uses

  • Dynamic trees and network flow. Sleator and Tarjan introduced heavy paths for link-cut trees, which speed up Dinic's maximum-flow algorithm to and are used in dynamic connectivity and in some network-simplex implementations for minimum-cost flow. HLD is the static, easy-to-implement special case.
  • Compact routing in trees. Thorup and Zwick's 2001 tree-routing scheme labels each node with the light edges on its root path; the light-edge lemma bounds the label to entries, so a router can forward a packet using only its own table and the destination's label. The same lemma underlies many informative labelling schemes (ancestry, distance, LCA labels), where XML databases and graph stores answer structural queries from short per-node labels. See BGP for the routing context where table size matters.
  • Distance labelling and oracles. Peleg's distance labels for trees ( bits per node) recursively split the tree at separators, which is centroid decomposition: each node stores its distance to each of its centroid ancestors — exactly the anc lists in the implementation. Planar-graph distance oracles generalise this with planar separators.
  • Union-by-size and "smaller half" algorithms. Union-find's union-by-size uses the small-to-large argument to bound tree height by ; Hopcroft's DFA minimisation processes the smaller of each split block to reach ; merging hash sets or sorted vectors smaller-into-larger is a common production idiom when accumulating per-group statistics.
  • Hierarchical aggregation. Systems that store hierarchies (organisation charts, file systems, category trees) and need "sum over a subtree" and "max along a management chain" with frequent updates use the same layout trick: a DFS numbering for subtrees, and either materialised paths or a chain decomposition for ancestor paths. The nested-set and materialised-path models in relational databases are the static versions.
  • Contest and interview reality. In industry interviews HLD and centroid decomposition appear rarely and mostly at companies with competitive-programming-style rounds; knowing when they apply and being able to sketch them is usually enough. In contests they are standard for Div. 1 / ICPC regional difficulty.

Pitfalls & edge cases

  • Recursion depth. Every structure here does DFS-like traversals over trees that can be paths of nodes. Use BFS orders and explicit stacks (as in all implementations above).
  • Heavy child must be visited first in the position-assigning DFS, or chains are not contiguous. With a stack, push the heavy child last.
  • Wrong comparison in the query loop. Compare depths of the chain heads, not of and . Comparing node depths can jump past the LCA.
  • Edge-valued queries must exclude the LCA's position; forgetting this double-counts the edge above the LCA.
  • Non-commutative aggregates need the two sides combined in path order with one side reversed.
  • Segment tree bounds. A subtree is ; using the Euler from a different DFS order (not heavy-first) is wrong.
  • Centroid: forgetting removed checks in BFS/DFS over components lets traversals leak into already-processed parts, giving time and wrong answers.
  • Centroid: recomputing sizes. Sizes must be recomputed for each component; reusing global sizes from the original root is wrong after the first level.
  • Counting paths: pairing within one subtree. Query all of a child subtree's depths before inserting any of them; and clear the counter only up to the maximum depth touched, or each level costs per centroid instead of , making the total quadratic.
  • Counting paths: unordered pairs. The one-sided "query then insert" pattern counts each unordered pair once; counting all pairs and subtracting same-subtree pairs is the alternative, but mixing the two double-counts.
  • Small-to-large: copying instead of swapping. Inheriting the big child's set must be (swap or move the reference). Copying it makes the algorithm quadratic.
  • Overflow. Path sums and pair counts ( for ) need 64-bit integers.

Variations

  • Path updates with lazy propagation. Replace the segment tree with a lazy one; each of the chain ranges becomes a range update. Codeforces 343D "Water Tree" combines subtree assignment and root-path assignment on the same positions.
  • HLD for LCA alone. Climb chains with the "deeper head" rule until the heads match; the shallower of and is the LCA. memory, per query, fast in practice.
  • Long-path decomposition. Choose the child with the deepest subtree instead of the largest; root paths can cross light edges, but merging depth-indexed arrays by inheriting the deepest child's array is total. Used for -th ancestor ladders and depth-DP problems (Codeforces 1009F).
  • Centroid decomposition with Fenwick trees per centroid answers "how many marked nodes within distance of " with updates in ; subtract the contribution counted through the same child (a second Fenwick tree per centroid, keyed by distance to the parent centroid).
  • Edge-centroid / top trees. Top trees (Alstrup, Holm, de Lichtenberg, Thorup, 2005) generalise both HLD and centroid ideas to dynamic forests with per operation.
  • Virtual trees (previous lesson) plus HLD or centroid decomposition handle queries that each touch a small set of nodes.
  • Rerooting DP solves "for every node as the root, compute " in and is often the simpler answer when a problem looks like it needs centroid decomposition.

Which tree technique to use

Problem shapeBest toolCostNotes
LCA / distance, static tree, moderate Binary lifting / also -th ancestor
LCA with very many queriesEuler tour + sparse table /
-th ancestor, jumps on a functional graphBinary liftingworks with cycles
static path sum / xorRoot prefix sums + LCA + LCAinvertible operations only
static path max / min / gcdBinary lifting with aggregates
subtree query with point updatesEuler tour (tin/tout) + Fenwick
path query with point updatesHLD + segment tree
path update + path queryHLD + lazy segment tree
path updates, read all at endDifference on tree + LCA each, final pass
count pairs / paths with a distance or weight conditionCentroid decomposition or
nearest marked node, within-distance countsCentroid decomposition to
per-subtree distinct / mode / multiset statsSmall-to-large or DSU on treeoffline
tree shape changes (link/cut)Link-cut trees / Euler-tour trees amortisedbeyond this module

Practice ladder

Each problem is described in my own words. Solutions are Python and are run as part of this page's checks against brute force.

1. Subordinates (CSES 1674) — Easy. Subtree sizes for every employee. Teaches the bottom-up size pass that both decompositions start with.

Hint

Process nodes in reverse BFS order and add each size to its parent's.

2. Finding a Centroid (CSES 2079) — Easy. Output any centroid. Teaches the walk toward the big child.

Hint

Compute sizes from any root; start at the root and move into a child of size more than while one exists.

Solution
import random
from collections import deque


def centroid(n: int, edges: list[tuple[int, int]]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    par, order = [-1] * n, [0]
    seen = [False] * n; seen[0] = True
    for x in order:
        for y in adj[x]:
            if not seen[y]:
                seen[y] = True; par[y] = x; order.append(y)
    size = [1] * n
    for x in reversed(order):
        if par[x] >= 0:
            size[par[x]] += size[x]
    c = 0
    while True:
        nxt = next((y for y in adj[c] if y != par[c] and 2 * size[y] > n), None)
        if nxt is None:
            return c
        c = nxt


def max_component_after_removing(n, edges, v):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    best, seen = 0, {v}
    for s in adj[v]:
        if s in seen:
            continue
        q, cnt = deque([s]), 0
        seen.add(s)
        while q:
            x = q.popleft(); cnt += 1
            for y in adj[x]:
                if y not in seen:
                    seen.add(y); q.append(y)
        best = max(best, cnt)
    return best


random.seed(1)
for _ in range(200):
    n = random.randint(1, 30)
    edges = [(random.randrange(i), i) for i in range(1, n)]
    c = centroid(n, edges)
    assert 2 * max_component_after_removing(n, edges, c) <= n
print("ok")

.

3. Minimize the Total Price of the Trips (LeetCode 2646) — Hard (on LeetCode, moderate here). Count how often each node is used by the trips, then halve the prices of a non-adjacent set. Teaches path counting on trees as a preprocessing step (difference on tree or one DFS per trip) followed by a tree DP.

Hint

Count visits per node (each trip's path), then a "house robber on a tree" DP: for each node, best total if halved or not halved, with halved nodes never adjacent.

4. Distinct Colors (CSES 1139) — Medium. Number of distinct colours in every subtree. Teaches small-to-large merging.

Hint

Each node inherits the largest child set (swap references) and inserts the others.

Solution
import random


def distinct_colors(n: int, edges: list[tuple[int, int]], color: list[int]) -> list[int]:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    par, order = [-1] * n, [0]
    seen = [False] * n; seen[0] = True
    for x in order:
        for y in adj[x]:
            if not seen[y]:
                seen[y] = True; par[y] = x; order.append(y)
    sets: list[set[int]] = [set() for _ in range(n)]
    ans = [0] * n
    for x in reversed(order):                    # children before parents
        sets[x].add(color[x])
        ans[x] = len(sets[x])
        p = par[x]
        if p >= 0:
            if len(sets[p]) < len(sets[x]):
                sets[p], sets[x] = sets[x], sets[p]   # keep the larger set at the parent
            sets[p] |= sets[x]                   # insert the smaller one
            sets[x] = set()
    return ans


random.seed(2)
for _ in range(200):
    n = random.randint(1, 25)
    edges = [(random.randrange(i), i) for i in range(1, n)]
    color = [random.randint(1, 5) for _ in range(n)]
    children = [[] for _ in range(n)]
    for a, b in edges:
        children[a].append(b)

    def collect(v):
        out, st = set(), [v]
        while st:
            x = st.pop(); out.add(color[x]); st.extend(children[x])
        return out

    assert distinct_colors(n, edges, color) == [len(collect(v)) for v in range(n)]
print("ok")

Every colour moves only into a set at least as large as its own: set insertions. (Here a parent's set is merged once per child as children finish, which keeps the argument intact: the smaller side is always the one inserted.)

5. Lomsat gelral (Codeforces 600E) — Medium/Hard. Sum of the dominating colours in every subtree. Teaches DSU on tree (sack) with a global counter, or small-to-large with frequency maps.

Hint

Maintain cnt[color], the current maximum frequency, and the sum of colours achieving it. Keep the heavy child's counts; re-add the light subtrees by iterating their Euler ranges.

6. Path Queries II (CSES 2134) — Hard. Point value changes and path maximum queries. Teaches the canonical HLD + segment tree.

Hint

Exactly HLD.set and HLD.path_max above, with fast I/O. In Python this needs PyPy and care.

7. QTREE - Query on a tree (SPOJ) — Hard. Change an edge's cost, or report the maximum edge cost on a path. Teaches edge values stored at the child and excluding the LCA position.

Hint

Map edge to its deeper endpoint. In the final same-chain step query with the shallower node.

8. Water Tree (Codeforces 343D) — Hard. Fill a subtree, empty a root path, ask whether a node is full. Teaches combining subtree ranges and path ranges on the same HLD positions with a lazy assignment segment tree.

Hint

"Fill " is a range assignment of 1 on 's subtree range; "empty " is assignment of 0 on the chain ranges from to the root; a query is a point read.

9. Distance in Tree (Codeforces 161D) — Medium. Count pairs at distance exactly , . Teaches the tree DP and is the warm-up for centroid decomposition.

Hint

dp[v][d] = nodes at depth below . When merging child into , add before adding shifted by one.

10. Fixed-Length Paths I (CSES 2080) — Hard. Count paths with exactly edges, up to . Teaches centroid decomposition with a depth counter.

Hint

At each centroid, cnt[0] = 1; for each child subtree, first add cnt[k - d] for every node at depth , then insert the depths. Reset only the touched prefix of cnt.

Solution
import random
from collections import deque


def count_paths(n: int, edges: list[tuple[int, int]], k: int) -> int:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    removed = [False] * n
    cnt = [0] * (n + 1)
    total = 0
    stack = [0]
    while stack:
        s = stack.pop()
        par, order = {s: -1}, [s]                 # find the centroid of s's component
        for x in order:
            for y in adj[x]:
                if not removed[y] and y != par[x]:
                    par[y] = x; order.append(y)
        size = {x: 1 for x in order}
        for x in reversed(order):
            if par[x] != -1:
                size[par[x]] += size[x]
        c = s
        while True:
            nxt = next((y for y in adj[c] if not removed[y] and y != par[c] and 2 * size[y] > len(order)), None)
            if nxt is None:
                break
            c = nxt
        removed[c] = True
        cnt[0], max_depth = 1, 0
        for y in adj[c]:                          # each child subtree: query, then insert
            if removed[y]:
                continue
            depths, q, seen = [], deque([(y, 1)]), {y}
            while q:
                x, d = q.popleft()
                if d > k:
                    continue
                depths.append(d)
                for z in adj[x]:
                    if not removed[z] and z not in seen:
                        seen.add(z); q.append((z, d + 1))
            for d in depths:
                total += cnt[k - d]
            for d in depths:
                cnt[d] += 1
                max_depth = max(max_depth, d)
        for d in range(max_depth + 1):            # reset only what was touched
            cnt[d] = 0
        for y in adj[c]:
            if not removed[y]:
                stack.append(y)
    return total


def brute(n, edges, k):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    res = 0
    for s in range(n):
        dist = [-1] * n; dist[s] = 0
        q = deque([s])
        while q:
            x = q.popleft()
            for y in adj[x]:
                if dist[y] < 0:
                    dist[y] = dist[x] + 1; q.append(y)
        res += sum(1 for t in range(s + 1, n) if dist[t] == k)
    return res


example = [(0, 1), (0, 2), (1, 3), (1, 4), (3, 5), (5, 6), (2, 7), (7, 8), (8, 9), (9, 10), (4, 11)]
assert count_paths(12, example, 3) == 11
random.seed(3)
for _ in range(200):
    n = random.randint(1, 25)
    edges = [(random.randrange(i), i) for i in range(1, n)]
    k = random.randint(1, n)
    assert count_paths(n, edges, k) == brute(n, edges, k)
print("ok")

: each level of the centroid tree touches each node once.

11. Xenia and Tree (Codeforces 342E) — Hard. Paint nodes red; report the distance to the nearest red node. Teaches per-centroid best distances.

Hint

CentroidXenia above is a complete solution apart from I/O (convert to 0-indexed, paint node 1 first).

12. Ciel the Commander (Codeforces 321C) — Hard. Assign letters A–Z so that any two nodes with the same letter have a better (earlier) letter on the path between them. Teaches that centroid-tree levels are exactly such a ranking, and the bound.

Hint

Give level- centroids the letter chr(ord('A') + i). Two nodes of the same level are in different components of some higher-level centroid that lies on their path.

Solution
import random


def ranks(n: int, edges: list[tuple[int, int]]) -> list[str]:
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    removed, level = [False] * n, [0] * n
    stack = [(0, 0)]
    while stack:
        s, lvl = stack.pop()
        par, order = {s: -1}, [s]
        for x in order:
            for y in adj[x]:
                if not removed[y] and y != par[x]:
                    par[y] = x; order.append(y)
        size = {x: 1 for x in order}
        for x in reversed(order):
            if par[x] != -1:
                size[par[x]] += size[x]
        c = s
        while True:
            nxt = next((y for y in adj[c] if not removed[y] and y != par[c] and 2 * size[y] > len(order)), None)
            if nxt is None:
                break
            c = nxt
        removed[c], level[c] = True, lvl
        for y in adj[c]:
            if not removed[y]:
                stack.append((y, lvl + 1))
    return [chr(ord("A") + l) for l in level]


def valid(n, edges, r):
    par = [-1] * n
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    order, seen = [0], [False] * n
    seen[0] = True
    for x in order:
        for y in adj[x]:
            if not seen[y]:
                seen[y] = True; par[y] = x; order.append(y)
    def path(u, v):
        au = []
        while u != -1:
            au.append(u); u = par[u]
        bv = []
        while v not in au:
            bv.append(v); v = par[v]
        return au[:au.index(v) + 1] + bv
    for u in range(n):
        for v in range(u + 1, n):
            if r[u] == r[v] and not any(r[w] < r[u] for w in path(u, v)):
                return False
    return True


random.seed(4)
for _ in range(100):
    n = random.randint(1, 30)
    edges = [(random.randrange(i), i) for i in range(1, n)]
    r = ranks(n, edges)
    assert valid(n, edges, r) and max(r) <= "Z"
print("ok")

; the centroid tree depth is at most .

13. Fixed-Length Paths II (CSES 2081) — Expert. Count paths whose length lies in . Teaches centroid decomposition with prefix sums over depth counts (or a Fenwick tree) and careful resetting.

Hint

At each centroid, for a node at depth add the number of earlier depths in , using a running prefix-sum array over cnt; process children in increasing order of subtree depth so each step costs .

14. Dominant Indices (Codeforces 1009F) — Expert. For every node, the smallest depth below it with the most nodes. Teaches long-path decomposition (inherit the deepest child's array) as an cousin of small-to-large.

Hint

Store each node's depth-count array reversed (or with an offset) so inheriting the deepest child's array is : prepend the node itself at depth 0 and merge the other children index by index.

Common mistakes & interview follow-ups

"Why is the number of chains on a path logarithmic?" Climbing a light edge more than doubles the subtree size (the heavy sibling is at least as big), so at most light edges lie on any root path; chain switches happen only on light edges.

"HLD or link-cut tree?" HLD if the tree shape is fixed: simpler, cache-friendly, . Link-cut trees if edges are added and removed, or if amortised is required.

"Why does centroid decomposition give and not ?" Each level of recursion partitions the nodes among disjoint components and does linear work in each; the component containing any node at least halves per level, so there are levels.

"Can a tree have two centroids?" Yes, exactly when an edge splits it into two halves of ; then both endpoints are centroids and they are adjacent. Otherwise it has one (Jordan 1869).

"Nearest marked node — why is the per-centroid minimum correct?" For the true nearest marked node , the centroid-tree LCA of and lies on the path between them, so one of 's centroid ancestors achieves the exact distance; every term is a real walk length, so none is too small.

"Can you avoid storing distances?" Yes: compute on the fly with an LCA (Euler tour + sparse table), at the cost of an LCA call per centroid ancestor.

"When is small-to-large better than DSU on tree?" Small-to-large is simpler when the per-subtree summary is a set or map; DSU on tree avoids allocating a structure per node and uses one global counter, which is faster and uses less memory for frequency-style queries.

Common mistakes: visiting the heavy child last; comparing node depths instead of head depths; forgetting the LCA exclusion for edge values; leaking traversals into removed centroids; resetting a whole counter per centroid; copying the big child's set; recursion on deep trees.

Quick quiz

  1. In the example, which edges are light, and how many light edges are on the root path of node 10?
Answer

Light edges: 0–2 and 1–4 (every other parent–child edge is heavy). Node 10's root path contains one light edge, 2–0.

  1. Why must the query loop advance the node whose chain head is deeper?
Answer

The chain with the deeper head cannot contain the LCA unless both nodes are on it; so the whole piece from that head down to the node lies on the path below the LCA and can be taken safely. Advancing by node depth can take a chain piece that extends above the LCA.

  1. The example tree has two centroids. Which, and why does the walk return 0?
Answer

0 and 1: removing 0 leaves components of 6 and 5; removing 1 leaves 3, 2 and 6. The walk starts at the root 0 and only moves into a child of size strictly greater than 6; child 1 has size exactly 6, so it stays at 0.

  1. When counting paths of length at a centroid, why query a child subtree before inserting it?
Answer

Two nodes in the same child subtree are connected by a path that does not pass through the centroid; pairing them here would count a wrong (too long) path, and their true path is counted at a deeper centroid.

  1. A node has 5 light edges on its root path. What is the minimum possible ?
Answer
  1. Let be the smallest tree containing a node with light edges on its root path. The top light edge leaves a parent whose light child's subtree needs at least nodes and whose heavy child is at least as large, so with , giving and (a perfect binary tree of depth 5, with ties broken so the path always takes the light child).

Further reading / sources

  • cp-algorithms: Heavy-light decomposition, Centroid decomposition, Lowest Common Ancestor.
  • D. D. Sleator & R. E. Tarjan, "A Data Structure for Dynamic Trees", Journal of Computer and System Sciences 26(3):362–391, 1983. DOI 10.1016/0022-0000(83)90006-5 — heavy paths and the light-edge lemma.
  • D. Harel & R. E. Tarjan, "Fast Algorithms for Finding Nearest Common Ancestors", SIAM Journal on Computing 13(2):338–355, 1984.
  • C. Jordan, "Sur les assemblages de lignes", Journal für die reine und angewandte Mathematik 70:185–190, 1869 — centroids (and centers) of trees.
  • R. J. Lipton & R. E. Tarjan, "A Separator Theorem for Planar Graphs", SIAM Journal on Applied Mathematics 36(2):177–189, 1979.
  • M. Thorup & U. Zwick, "Compact Routing Schemes", SPAA 2001 — tree routing with heavy paths.
  • D. Peleg, "Proximity-Preserving Labeling Schemes", Journal of Graph Theory 33(3):167–176, 2000 — distance labels via separators.
  • S. Alstrup, J. Holm, K. de Lichtenberg & M. Thorup, "Maintaining Information in Fully Dynamic Trees with Top Trees", ACM Transactions on Algorithms 1(2):243–264, 2005.
  • J. Hopcroft, "An n log n algorithm for minimizing states in a finite automaton", 1971 — the "smaller half" argument.
  • Codeforces blog by Arpa, "[Tutorial] Sack (dsu on tree)" (2016) — DSU on tree as used in contests.
  • A. Laaksonen, Competitive Programmer's Handbook, chapter 18 (tree queries) and Guide to Competitive Programming (Springer, 2nd ed.), sections on centroid decomposition and heavy-light decomposition.

Prev: LCA, Binary Lifting & Euler Tour · Next: Spatial Trees: Interval Trees, k-d Trees, Quadtrees & R-trees

Related: Module 3 — Trees · Segment Trees in Depth · Fenwick Trees · Sparse Tables, Sqrt Decomposition & Mo's Algorithm · Trees (Overview) · Graphs · Advanced Data Structures · DSA: Zero to Mastery