xii. Top Trees

A top tree represents a tree as a hierarchy of clusters (connected edge sets with at most two boundary vertices), built from single edges by two merges: compress (two clusters sharing a degree-2 boundary vertex on a path become one path cluster) and rake (a cluster hanging off a vertex is absorbed into a neighbouring cluster). Any information that can be merged under these two operations, which covers path and subtree aggregates, diameters, centres, medians and tree DPs, is then available.

• Static top tree (fixed shape, changing vertex data): heavy paths merged by compress and light children merged by rake, both weight-balanced. Depth $O(\log n)$, so a vertex update recomputes $O(\log n)$ clusters. This is the practical “dynamic DP on a tree” tool, an alternative to HLD plus matrix-product segment trees (Dynamic DP).
• Dynamic top tree (link, cut, reroot): self-adjusting (splay-based) top trees, $O(\log n)$ amortized, supporting path and subtree aggregates at once.

Static top tree

Ops defines the cluster algebra: P is a path cluster (a stretch of a heavy path with everything hanging below it, boundaries = its top and bottom vertices), Q is a point cluster (light subtrees hanging from one vertex).

// rooted tree split into heavy paths: a path cluster (type P) is a stretch of a heavy path with everything
// hanging below it, a point cluster (type Q) is a set of light subtrees hanging from one vertex. merging is
// balanced by subtree sizes, so the top tree has depth O(log n) and an update recomputes O(log n) nodes.
// Ops must provide (top = side closer to the root):
//   P vertex(int v)                    v alone (no light children)
//   P addVertex(const Q& light, int v) v with its light children
//   P compress(const P& top, const P& bottom)
//   Q addEdge(const P& path)           a light child's whole subtree seen from its parent
//   Q rake(const Q& a, const Q& b)
template <class P, class Q, class Ops>
struct StaticTopTree {
    enum Type { Vertex, AddVertex, Compress, AddEdge, Rake };
    int n, root;
    Ops ops;
    vector<int> par, lch, rch, vtx, nodeOf, heavy, siz;
    vector<Type> type;
    vector<P> pv;
    vector<Q> qv;
 
    StaticTopTree(const vector<vector<int>>& adj, Ops o, int r = 0) : n(adj.size()), ops(o), nodeOf(n), heavy(n, -1), siz(n, 1) {
        vector<int> parent(n, -1), order = {r};
        parent[r] = r;
        for (int i = 0; i < (int)order.size(); i++) {
            for (int v : adj[order[i]]) {
                if (parent[v] == -1) parent[v] = order[i], order.push_back(v);
            }
        }
        for (int i = n - 1; i > 0; i--) siz[parent[order[i]]] += siz[order[i]];
        vector<vector<int>> children(n);
        for (int i = 1; i < n; i++) children[parent[order[i]]].push_back(order[i]);
        for (int v = 0; v < n; v++) {
            for (int c : children[v]) {
                if (heavy[v] == -1 || siz[c] > siz[heavy[v]]) heavy[v] = c;
            }
        }
        auto light = [&](int v) {
            vector<int> res;
            for (int c : children[v]) {
                if (c != heavy[v]) res.push_back(c);
            }
            return res;
        };
        // iterative build: process vertices bottom-up so every light child's path exists before its parent
        vector<int> pathNode(n, -1);   // node of the heavy path starting at v (v = top of its path)
        for (int i = n - 1; i >= 0; i--) {
            int top = order[i];
            if (top != r && heavy[parent[top]] == top) continue;   // not the top of a heavy path
            vector<pair<int, int>> items;                           // (node, weight) along the path
            for (int v = top; v != -1; v = heavy[v]) {
                vector<pair<int, int>> ls;
                for (int c : light(v)) ls.push_back({make(AddEdge, pathNode[c], -1, -1), siz[c]});
                int node;
                if (ls.empty()) {
                    node = make(Vertex, -1, -1, v);
                } else {
                    node = make(AddVertex, merge(ls, 0, ls.size(), Rake), -1, v);
                }
                nodeOf[v] = node;
                items.push_back({node, siz[v] - (heavy[v] == -1 ? 0 : siz[heavy[v]])});
            }
            pathNode[top] = merge(items, 0, items.size(), Compress);
        }
        root = pathNode[r];
        par.resize(type.size(), -1);
        for (int x = 0; x < (int)type.size(); x++) {
            if (lch[x] != -1) par[lch[x]] = x;
            if (rch[x] != -1) par[rch[x]] = x;
        }
        pv.resize(type.size()), qv.resize(type.size());
        for (int x = 0; x < (int)type.size(); x++) pull(x);   // children always have smaller ids
    }
 
    int make(Type t, int l, int rr, int v) {
        type.push_back(t), lch.push_back(l), rch.push_back(rr), vtx.push_back(v);
        return type.size() - 1;
    }
    int merge(const vector<pair<int, int>>& items, int l, int r, Type t) {   // balanced by weight
        if (r - l == 1) return items[l].first;
        ll total = 0;
        for (int i = l; i < r; i++) total += items[i].second;
        int m = l + 1;
        ll acc = items[l].second;
        while (m + 1 < r && 2 * (acc + items[m].second) <= total) acc += items[m++].second;
        int a = merge(items, l, m, t), b = merge(items, m, r, t);
        return make(t, a, b, -1);
    }
 
    void pull(int x) {
        switch (type[x]) {
            case Vertex: pv[x] = ops.vertex(vtx[x]); break;
            case AddVertex: pv[x] = ops.addVertex(qv[lch[x]], vtx[x]); break;
            case Compress: pv[x] = ops.compress(pv[lch[x]], pv[rch[x]]); break;
            case AddEdge: qv[x] = ops.addEdge(pv[lch[x]]); break;
            case Rake: qv[x] = ops.rake(qv[lch[x]], qv[rch[x]]); break;
        }
    }
 
    void update(int v) {   // call after the data of vertex v changed
        for (int x = nodeOf[v]; x != -1; x = par[x]) pull(x);
    }
    const P& get() const { return pv[root]; }   // the whole tree as one path cluster
};

Example: maximum weight independent set with point updates of vertex weights.

struct MisOps {                                           // max weight independent set with changing vertex weights
    static constexpr ll NEG = LLONG_MIN / 4;
    struct P { ll d[2][2]; };                             // d[top taken][bottom taken] for a heavy-path stretch
    struct Q { ll any = 0, free = 0; };                   // light subtrees: best overall / best with their roots not taken
    const vector<ll>& w;
    P vertex(int v) const { return addVertex(Q{}, v); }
    P addVertex(const Q& q, int v) const { P p; p.d[0][0] = q.any; p.d[1][1] = w[v] + q.free; p.d[0][1] = p.d[1][0] = NEG; return p; }
    P compress(const P& a, const P& b) const {            // a above b; a's bottom vertex is adjacent to b's top vertex
        P r; for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++) {
            r.d[x][y] = NEG;
            for (int s = 0; s < 2; s++) for (int t2 = 0; t2 < 2; t2++) if (!(s && t2) && a.d[x][s] > NEG && b.d[t2][y] > NEG) r.d[x][y] = max(r.d[x][y], a.d[x][s] + b.d[t2][y]);
        }
        return r;
    }
    Q addEdge(const P& p) const { Q q; q.free = max(p.d[0][0], p.d[0][1]); q.any = max({q.free, p.d[1][0], p.d[1][1]}); return q; }
    Q rake(const Q& a, const Q& b) const { return {a.any + b.any, a.free + b.free}; }
};
// StaticTopTree<MisOps::P, MisOps::Q, MisOps> st(adj, MisOps{w}, root);  w[v] = x; st.update(v);
// answer = max over the four entries of st.get().d

Proof: the cluster algebra and $O(\log n)$ depth

Algebra (independent set): a path cluster’s table gives the best weight inside it for each choice of its top and bottom vertices being taken; compressing two consecutive stretches forbids taking both the upper stretch’s bottom and the lower stretch’s top (they are adjacent), and sums the rest, since the two clusters share no vertices. addVertex attaches a vertex’s light subtrees, which may be taken freely if the vertex is not taken and must have their roots free if it is; addEdge summarises a light child’s whole heavy path (top = the child) as (best overall, best with the child free); rake adds independent subtrees. Every cluster combines disjoint parts, so the root cluster is the whole tree’s optimum.

Depth: a weight-balanced merge of items with total weight $W$ splits them into two groups of weight at most about $W/2$ plus one item, so a node of the merge tree at depth $k$ (inside that merge) has weight $\le W/2^{\lfloor k/2\rfloor }$, roughly. Weights are subtree sizes of the light parts (for compress) and of light children (for rake). Following a vertex’s clusters up to the root alternates between merges inside one heavy path or one rake group and jumps across a light edge; the weights along the way telescope, because each merge level about halves the weight relative to the enclosing total and each light edge at least halves the subtree size. Summing, the depth is $O(\log n)$, and an update recomputes one node per level.

Dynamic top tree

Vertices and edges are nodes; link(e, u, v) uses a fresh edge node e (set e->val first). Path clusters are compress nodes, path vertices are leaves with raked children, non-path edges are rake nodes; each node keeps path (sum over the cluster path, vertices and edges) and all (sum over the whole cluster). To carry other information, edit the payload block (update, doFlipPath for direction-dependent data).

struct TopTreeNode;
using TopPtr = TopTreeNode*;
 
struct TopTreeNode {
    TopPtr p = nullptr;
    array<TopPtr, 3> c{nullptr, nullptr, nullptr};
    bool isPath = false, isVert = false, flipPath = false;
 
    // ---- payload (edit here) ----
    ll val = 0;          // weight of this vertex / edge
    ll path = 0, all = 0;
 
    void doFlipPath() { flipPath ^= 1; }   // sums are symmetric; swap directional data here
    void downdate() {
        if (flipPath) {
            if (!isVert) {
                for (int i = 0; i < 2; i++) {
                    if (c[i]) c[i]->doFlipPath();
                }
            }
            swap(c[0], c[1]);
            flipPath = false;
        }
    }
    void update() {
        auto A = [](TopPtr x) { return x ? x->all : 0LL; };
        if (isPath && !isVert) {   // compress(c[0], self, c[1])
            path = c[0]->path + val + c[1]->path;
            all = c[0]->all + val + c[1]->all;
        } else if (isVert) {       // self + rake(c[0], c[1])
            path = val;
            all = val + A(c[0]) + A(c[1]);
        } else {                   // rake(c[0], self + c[2], c[1])
            path = 0;
            all = val + c[2]->all + A(c[0]) + A(c[1]);
        }
    }
    // ---- end of payload ----
 
    void initVertex(ll w = 0) {
        isPath = isVert = true;
        val = w;
        update();
    }
 
    int d() const {
        if (!p) return -1;
        for (int i = 0; i < 3; i++) {
            if (this == p->c[i]) return i;
        }
        assert(false);
        return -1;
    }
    bool r() const { return !p || p->isPath != isPath; }   // root of a rake or compress tree
 
    void downdateAll() {
        if (p) p->downdateAll();
        downdate();
    }
    TopPtr updateAll() {
        TopPtr cur = this;
        cur->update();
        while (cur->p) cur = cur->p, cur->update();
        return cur;
    }
 
    static void setLink(TopPtr x, TopPtr y, int dir) {
        if (y) y->p = x;
        if (dir != -1) x->c[dir] = y;
    }
 
    void rot() {
        TopPtr pa = p;
        int x = d();
        TopPtr ch = c[!x];
        setLink(pa->p, this, pa->d());
        setLink(pa, ch, x);
        setLink(this, pa, !x);
        pa->update();
    }
    void rot2(int cd) {
        if (d() == cd) {
            rot();
            return;
        }
        TopPtr pa = p;
        int x = d();
        TopPtr ch = c[cd]->c[!x];
        setLink(pa->p, this, pa->d());
        setLink(pa, ch, x);
        setLink(this->c[cd], pa, !x);
        pa->update();
    }
    void splayDir(int x) {
        while (!r() && d() == x) {
            if (!p->r() && p->d() == x) p->rot();
            rot();
        }
    }
    void splay2(int cd) {
        while (!r()) {
            if (!p->r()) {
                if (p->d() == d()) p->rot();
                else rot2(cd);
            }
            rot2(cd);
        }
    }
    void splay2() { p->splay2(d()); }
    void splayVert() {
        if (r()) return;
        p->splayDir(d());
        if (p->r()) return;
        if (d() == 1) p->rot();
        p->splay2();
    }
    void splay() {
        while (!r()) {
            if (!p->r()) {
                if (p->d() == d()) p->rot();
                else rot();
            }
            rot();
        }
    }
 
    TopPtr cutRight() {
        splayVert();
        if (r() || d() == 1) return nullptr;
        TopPtr pa = p;
        setLink(pa->p, this, pa->d());
        pa->isPath = false;
        pa->c[2] = pa->c[1];
        for (int i = 0; i < 2; i++) setLink(pa, c[i], i);
        c[0] = nullptr;
        setLink(this, pa, 1);
        pa->update();
        return pa;
    }
 
    TopPtr spliceNonPath() {
        splay();
        p->cutRight();
        if (!p->isPath) rot();
        TopPtr pa = p;
        setLink(pa->p, this, pa->d());
        for (int i = 0; i < 2; i++) setLink(pa, c[i], i);
        c[1] = c[2];
        setLink(this, pa, 0);
        c[2] = nullptr;
        isPath = true;
        pa->update();
        return pa;
    }
 
    TopPtr spliceAll() {
        TopPtr res = nullptr;
        for (TopPtr cur = this; cur; cur = cur->p) {
            if (!cur->isPath) res = cur->spliceNonPath();
        }
        return res;
    }
 
    TopPtr expose() {   // returns the topmost vertex spliced into (used by lca)
        downdateAll();
        TopPtr res = spliceAll();
        cutRight();
        updateAll();
        return res;
    }
 
    TopPtr exposeEdge() {
        downdateAll();
        TopPtr v = isPath ? c[1] : c[2];
        v->downdate();
        while (!v->isVert) v = v->c[0], v->downdate();
        TopPtr res = v->spliceAll();
        v->cutRight();
        v->updateAll();
        return res;
    }
 
    TopPtr meldPathEnd() {
        TopPtr rt = this;
        while (true) {
            rt->downdate();
            if (rt->isVert) break;
            rt = rt->c[1];
        }
        rt->splayVert();
        if (rt->c[0] && rt->c[1]) {
            TopPtr ch = rt->c[1];
            while (true) {
                ch->downdate();
                if (!ch->c[0]) break;
                ch = ch->c[0];
            }
            ch->splay();
            setLink(ch, rt->c[0], 0);
            rt->c[0] = nullptr;
            ch->update();
        } else if (rt->c[0]) {
            rt->c[1] = rt->c[0];
            rt->c[0] = nullptr;
        }
        return rt->updateAll();
    }
 
    void makeRoot() {
        expose();
        TopPtr rt = this;
        while (rt->p) rt = rt->p;
        rt->doFlipPath();
        rt->meldPathEnd();
        expose();
    }
 
    TopPtr getRoot() {
        expose();
        TopPtr v = this;
        while (v->p) v = v->p;
        v->downdate();
        while (!v->isVert) v = v->c[0], v->downdate();
        v->expose();
        return v;
    }
};
 
bool connected(TopPtr a, TopPtr b) { return a->getRoot() == b->getRoot(); }
 
// links v2 below v1 with the (fresh) edge node e; set e->val before calling
void link(TopPtr e, TopPtr v1, TopPtr v2) {
    e->isPath = true, e->isVert = false;
    v1->expose();
    while (v1->p) v1 = v1->p;
    v2->makeRoot();
    TopTreeNode::setLink(e, v1, 0);
    TopTreeNode::setLink(e, v2, 1);
    e->update();
}
 
pair<TopPtr, TopPtr> cut(TopPtr e) {
    e->exposeEdge();
    TopPtr l = e->c[0], r = e->c[1];
    e->c[0] = e->c[1] = nullptr;
    l->p = r->p = nullptr;
    l = l->meldPathEnd();
    return {l, r};
}
 
TopPtr getPath(TopPtr a, TopPtr b) {   // cluster whose `path` is the a..b path
    a->makeRoot();
    b->expose();
    if (a == b) return b;
    return b->p;
}
 
TopPtr getSubtree(TopPtr rt, TopPtr v) {   // vertex v; v->all = its subtree when rooted at rt
    rt->makeRoot();
    v->expose();
    return v;
}
 
TopPtr lca(TopPtr a, TopPtr b) {
    a->expose();
    TopPtr r = b->expose();
    return r ? r : b;
}

Call	Meaning
link(&edge[i], &vert[u], &vert[v])	add edge $u$–$v$ (fresh edge node, val = weight)
cut(&edge[i])	remove that edge
getPath(&vert[a], &vert[b])->path	sum of vertex and edge weights on the $a$–$b$ path
getSubtree(&vert[r], &vert[x])->all	sum over $x$‘s subtree (vertices and the edges inside it) when rooted at $r$
vert[r].makeRoot(); lca(&vert[a], &vert[b])	LCA with respect to root $r$
point update	vert[x].expose(); vert[x].val = w; vert[x].updateAll(); (edges: exposeEdge)

Proof sketch: self-adjusting top trees

The representation is a hierarchy of splay trees: compress trees (one per exposed path, ordered along the path) whose leaves carry rake trees of the clusters hanging off each path vertex. expose(v) makes the root-to-$v$ path the root compress path by splicing each non-path ancestor in (spliceNonPath, the analogue of a link-cut access jump) and cutting off the part below $v$ (cutRight); makeRoot additionally reverses the root path (doFlipPath), exactly as evert in a link-cut tree. After exposing, the root cluster’s path field is the aggregate along the exposed path and a vertex’s all field the aggregate of what hangs below it, which gives getPath and getSubtree. The amortized $O(\log n)$ bound follows the link-cut analysis: the number of splices per expose is bounded by a heavy–light argument, and the splay rotations telescope under the sum-of-log-sizes potential (Tarjan–Werneck, self-adjusting top trees).

When to use what

Situation	Tool
static tree, path updates and queries	HLD + segment tree
static tree, a tree DP under point updates	static top tree (or HLD + matrix products)
link / cut with path aggregates	Link-Cut Tree
link / cut with subtree aggregates	Euler Tour Tree or link-cut with virtual subtrees
link / cut with both, or diameter / centre / median of a dynamic tree	dynamic top tree

The dynamic top tree above is a port of ecnerwala’s top tree, verified against DMOJ ds5 and CF 1413F (Benq’s verification problem for this exact structure) — use those if you need to stress-test your own port. For the static top tree, a typical $P$ for sums along paths is an affine map $x\mapsto ax+b$ per cluster rather than a fixed-size table; to support rerooting (not just a fixed root), extend $P$ to also carry the reversed-path data.

Tree contraction: rake and compress

Tree contraction (Miller–Reif) evaluates a tree computation in $O(\log n)$ rounds by two local operations: rake removes leaves (folding a leaf’s value into its parent), compress contracts a vertex of degree 2 into its neighbour (composing the two edge functions). It is the parallel algorithm behind expression-tree evaluation, and the static top tree above is exactly a balanced sequential schedule of the same two operations (compress = path cluster merge, rake = point cluster merge).

For expression trees, each edge carries a function from a closed class (e.g. linear maps $x\mapsto ax+b$ for $+,\times$ expressions); rake applies a known child value to the parent operator, producing such a map on the remaining edge, and compress composes the two maps of a chain vertex. Both keep the class closed, so the final root value is exact.

Proof: $O(\log n)$ rounds

Let a round rake all current leaves, then compress an independent set of degree-2 chain vertices chosen by random coin flips (a vertex compresses if its coin is heads and its parent’s is tails, so no two adjacent vertices compress at once). In a tree with $\ell$ leaves, the number of branching vertices (degree $\ge 3$) is less than $\ell$, so the vertices that are neither leaves nor branching, i.e. chain vertices, number $n-O(\ell )$. Raking removes all $\ell$ leaves; each chain vertex is compressed with probability $\frac{1}{4}$. So a round removes at least a constant fraction of the vertices in expectation, and after $O(\log n)$ rounds one vertex remains (with high probability by a Chernoff bound over rounds). Work per round is linear in the current size, $O(n)$ total.