Top Trees, in depth: clusters, rake and compress, expose, and a static top tree for dynamic tree DP

What paths and subtrees cannot answer

Suppose you want the diameter of a tree that gains and loses edges. A link-cut tree aggregates along one path, but the diameter depends on every branch. An Euler-tour tree aggregates a subtree, but the diameter is not a sum over a sequence. You can patch virtual-subtree data into a link-cut tree, but each new query needs a new, careful patch.

Top trees separate the parts. The structure handles shape: which pieces merge, in what order, with height O(log n). You supply meaning: what a cluster stores and how two summaries combine. Paths, subtrees, diameter, centre and median all reuse the machinery. Link-cut trees in depth and Euler tours and Euler-tour trees cover the two specialised structures this generalises.

Clusters and boundary vertices

Take a tree T and pick at most two vertices of it as external boundary vertices. A cluster is a connected set of edges. Its boundary is made of two kinds of vertex: those that touch an edge outside the cluster, plus any external boundary vertex it contains. The rule that makes everything work is that a cluster's boundary has at most two vertices.

A cluster with two boundary vertices is a path cluster; path information is stored along the path between them. A cluster with one is a point cluster: a branch hanging from a single vertex. The whole tree is a cluster whose boundary is the external boundary vertices.

A top tree is a binary tree over clusters. Its leaves are the edges of T, each internal node is the union of its two children, and the root is all of T. Two clusters merge only if they share a vertex and the result keeps at most two boundary vertices.

Rake, compress and user summaries

Compress joins two path clusters meeting at a vertex x where nothing else attaches; x leaves the boundary and the paths concatenate. Rake folds a point cluster into a neighbour sharing its boundary vertex. These are the rake and compress steps of Miller and Reif's parallel tree contraction; a top tree records one schedule of height O(log n).

You supply a leaf builder and one function per merge. This summary maintains the diameter of an edge-weighted tree: for boundaries u and v it stores the path length, the farthest distance from each boundary, and the diameter inside the cluster.

def leaf(u, v, w):                    # one edge u-v of weight w
    return dict(len=w, far_u=w, far_v=w, diam=w)

def compress(a, b):                   # a has boundaries (u, x), b has (x, v)
    return dict(len=a["len"] + b["len"],
                far_u=max(a["far_u"], a["len"] + b["far_u"]),   # b.far_u: from x
                far_v=max(b["far_v"], b["len"] + a["far_v"]),   # a.far_v: from x
                diam=max(a["diam"], b["diam"], a["far_v"] + b["far_u"]))

def rake(branch, b):                  # branch hangs at x = b's u-boundary
    return dict(len=b["len"],
                far_u=max(b["far_u"], branch["far_u"]),
                far_v=max(b["far_v"], b["len"] + branch["far_u"]),
                diam=max(b["diam"], branch["diam"], b["far_u"] + branch["far_u"]))

A summary works only if every merged field is computable from the children's fields.

Link, cut, expose and non-local search

The dynamic interface has three operations. link(v, w) adds an edge between two trees. cut(v, w) removes one. expose(v, w) makes v and w the external boundary vertices and returns the root cluster, whose cluster path is now the v to w path. Each operation dismantles and re-merges the O(log n) clusters touching the affected vertices, calling your merge functions, and a split function before each dismantle so lazy updates reach the children.

max_edge_on_path(v, w):
    C = expose(v, w)          # null if v and w are in different trees
    return C.max_on_path      # compress: max(a, b); rake: keep the path child's value

add_to_path(v, w, delta):
    C = expose(v, w)
    C.max_on_path += delta; C.lazy += delta   # split() pushes lazy to children later

Non-local search is what top trees add. To find the centre (the vertex minimising the maximum distance to others), start at the root cluster and, at each level, use the two children's summaries to decide which must contain the answer: O(1) per level, O(log n) in total. Comparing far distances either side of the shared vertex decides the centre; comparing subtree weights decides the median. Test searches against brute force.

Implementations and what they cost

Several implementations exist, and they make different trade-offs:

An experimental study by Tarjan and Werneck (Dynamic Trees in Practice, ACM Journal of Experimental Algorithmics, 2009) found that a link-cut tree is usually the fastest choice when only path operations are needed. Top trees pay a constant-factor price for being more general. Use a top tree when your query is not a plain path aggregate, not because it is the most general option.

A static top tree in code

Many workloads keep the shape fixed and change weights: budgets on an organisation chart, link costs on a network, a tree DP refreshed after point updates. Build the top tree once: split the tree into heavy paths, compress each path in a binary tree balanced by subtree size, and rake light children the same way. Depth is O(log n), and an update recomputes only one leaf's ancestors.

The example maintains a maximum-weight independent set (no two chosen vertices adjacent; weights may be negative). A path cluster is a 2 by 2 (max, +) matrix mapping the best values below its bottom vertex (child excluded, included) to those at its top. Compress is matrix multiplication; rake adds light-child contributions.

NEG = float("-inf")

def mul(a, b):  # max-plus 2x2 product: (a*b)[i][j] = max over k of a[i][k] + b[k][j]
    return [[max(a[i][0] + b[0][j], a[i][1] + b[1][j]) for j in (0, 1)] for i in (0, 1)]

class StaticTopTree:
    # Max-weight independent set of a rooted tree (parent[v] < v), O(log n) per update.
    def __init__(self, parent, w):
        n = len(parent)
        self.w, self.kids, self.size = list(w), [[] for _ in range(n)], [1] * n
        for v in range(n - 1, 0, -1):
            self.kids[parent[v]].append(v)
            self.size[parent[v]] += self.size[v]
        self.heavy = [max(k, key=self.size.__getitem__, default=-1) for k in self.kids]
        self.kind, self.ch, self.up, self.val = [], [], [], []
        self.vert, self.vnode = {}, [0] * n
        self.root = self.path(0)

    def node(self, kind, ch, vertex=None):
        i = len(self.kind)
        self.kind.append(kind); self.ch.append(ch); self.up.append(-1); self.val.append(None)
        for c in ch:
            self.up[c] = i
        if vertex is not None:
            self.vert[i], self.vnode[vertex] = vertex, i
        self.pull(i)
        return i

    def merge(self, items, weights, kind):  # split at the weighted midpoint
        if len(items) == 1:
            return items[0]
        half, acc, k = sum(weights) / 2, weights[0], 1
        while k < len(items) - 1 and acc + weights[k] <= half:
            acc += weights[k]; k += 1
        return self.node(kind, [self.merge(items[:k], weights[:k], kind),
                                self.merge(items[k:], weights[k:], kind)])

    def path(self, h):  # builds h's heavy path; returns the point cluster of h's subtree
        nodes, weights, v = [], [], h
        while v != -1:
            light = [c for c in self.kids[v] if c != self.heavy[v]]
            bundle = [self.merge([self.node("light", [self.path(c)]) for c in light],
                                 [self.size[c] for c in light], "rake")] if light else []
            nodes.append(self.node("vertex", bundle, v))
            weights.append(1 + sum(self.size[c] for c in light))
            v = self.heavy[v]
        return self.node("point", [self.merge(nodes, weights, "compress")])

    def pull(self, i):
        k, ch = self.kind[i], self.ch[i]
        if k == "vertex":      # path cluster: matrix from (below0, below1) to (top0, top1)
            a, b = self.val[ch[0]] if ch else (0, 0)
            self.val[i] = [[a, a], [self.w[self.vert[i]] + b, NEG]]
        elif k == "compress":  # upper cluster times lower cluster
            self.val[i] = mul(self.val[ch[0]], self.val[ch[1]])
        elif k == "point":     # close the path: nothing hangs below its last vertex
            m = self.val[ch[0]]
            self.val[i] = (m[0][0], m[1][0])
        elif k == "light":     # a child subtree as a contribution to its parent
            p0, p1 = self.val[ch[0]]
            self.val[i] = (max(p0, p1), p0)
        else:                  # rake: two bundles of light children add up
            (a1, b1), (a2, b2) = self.val[ch[0]], self.val[ch[1]]
            self.val[i] = (a1 + a2, b1 + b2)

    def set_weight(self, v, x):
        self.w[v] = x
        i = self.vnode[v]
        while i != -1:
            self.pull(i)
            i = self.up[i]

    def answer(self):
        return max(self.val[self.root])

A vertex stores light-child totals a (best values) and b (values with the child excluded). Excluded, it scores a plus the better value below; included, its weight plus b plus the excluded value below. On random 100,000-vertex trees this cluster tree was under 50 levels deep; a plain path gave 19.

Worked example: seven vertices

Take seven vertices with parents [-, 0, 0, 1, 1, 2, 3] and weights [3, 4, 5, 2, 6, 1, 7]. The heavy paths are 0-1-3-6, 2-5 and 4. Work from the bottom. Path 2-5 closes to (excluded 1, included 5), so vertex 0 receives the light contribution (5, 1). Vertex 4 closes to (0, 6), so vertex 1 receives (6, 0). Along the main path, vertex 6 gives (0, 7). Vertex 3 gives (7, 2). Vertex 1 gives (6 + max(7, 2), 4 + 0 + 7) = (13, 11). Vertex 0 gives (5 + max(13, 11), 3 + 1 + 13) = (18, 17). The answer is 18: the set {6, 4, 2}.

Now set vertex 4's weight to 1. Its contribution to vertex 1 becomes (1, 0), vertex 1 gives (8, 11), and vertex 0 gives (5 + 11, 3 + 1 + 8) = (16, 12): the answer is 16, the set {6, 1, 2}. The code agreed with an O(n) DP on 400 random trees with 30 updates each.

Failure modes

• A summary that is not closed under merging. Asking for the diameter but storing only one far distance gives answers that are right on paths and wrong on stars. Test the summary on stars, caterpillars and paths against brute force before you trust it.
• Confusing the two boundaries. Compress code that assumes the left child holds the upper boundary works until a reversal or an expose swaps them. Self-adjusting implementations must keep an orientation bit and swap the fields of any asymmetric summary when that bit flips.
• Lazy values that are not pushed down. Path updates must be pushed to the children in split before any restructuring happens, or later merges will combine stale children.
• Phantom vertices. Ternarised implementations add dummy vertices; exclude them from counts and medians.

Trade-offs

For fully dynamic connectivity, top trees are one component inside larger structures. See dynamic connectivity in depth. If you only need path queries on a fixed tree, heavy-light decomposition is simpler again. The static top tree is heavy-light decomposition with the per-path segment trees replaced by balanced merges, which removes a log factor.

What to do next

1. Write down the query you need, then design the cluster summary and both merge functions on paper.
2. Brute-force the summary: enumerate all merges on random small trees and compare against direct computation.
3. If the tree's shape is fixed, implement the static top tree above and swap in your own matrix or summary.
4. If links and cuts are required and only path queries matter, use a link-cut tree; otherwise read Tarjan and Werneck's self-adjusting top trees.
5. Add a stress test with paths, stars and caterpillars of a million vertices to check depth and stack use.
6. Profile against an O(n) recomputation at your real tree size. Below a few thousand vertices it may win.