Hello Codeforces!

Some of you might know BottleneckTree.h from my KACTL fork (although it's a little obscure for an ICPC notebook; oh well). Adrian Budău and I wrote it in 2021. The header says the complexity is "probably $$$O(\log n)$$$ amortized". It all started from a 2020 solution by Rajarshi Basu (more on that at the end). After about 6 years of on-and-off thinking about it, and with the help of Claude, we finally have an answer: it's not :). There are inputs where it takes $$$\Omega(\sqrt n)$$$ per operation.

The good news is that a small change in the main loop fixes it, and this time we have a proof. We wrote a paper about it: Incremental Minimum Spanning Trees on a Napkin. I think the structure is super elegant and short enough to be useful in contests, so I'm writing a blog about it.

Prerequisites: none, really. It helps to know link-cut trees for the last part.

The problem

Edges come one by one, online. We want to support two operations:

• AddEdge(x, y, c): add edge $$$(x, y)$$$ with cost $$$c$$$. Return the cost of the edge that gets removed from the MST. This is $$$c$$$ if the new edge doesn't enter the MST, and INF if $$$x$$$ and $$$y$$$ were not connected.
• Query(x, y): return the smallest possible maximum edge cost on a path from $$$x$$$ to $$$y$$$.

The usual way to do this is with a link-cut tree. That's $$$O(\log n)$$$ amortized, but it's long to code and slow in practice.

You might also know this blog by not_amir from 2024. It describes a "weighted DSU" for the same problem. It uses the same kind of tree as us: a parent and a weight for each vertex. It links vertices by random indices, and it has no proof. Our structure is different: it uses rotations, it is deterministic, and it stores only link and cost. That blog also has a nice list of problems and some extra operations, so check it out. Maybe the proof here helps with that one too?

Implementation

const int INF = 1e9;
struct BottleneckTree {
  vector<int> link, cost;   // all inserted costs must be < INF
  BottleneckTree(int n) : link(n, 0), cost(n, INF) {
    link[0] = -1; cost[0] = INF + 1;
  }
  void rot(int x) {
    int p = link[x], g = link[p];
    swap(cost[x], cost[p]);
    link[x] = g, link[p] = x;
  }
  void skip(int x) { link[x] = link[link[x]]; }
  void access(int x) {
    for (int p = link[x]; p != -1; p = link[x]) {
      int g = link[p];
      if (cost[x] <= cost[p]) rot(x);                  // (A)
      else if (cost[p] > cost[g]) skip(p), skip(x);    // (B)
      else if (cost[g] <= cost[x]) rot(p), skip(x);    // (C)
      else skip(x);                                    // (D)
    }
  }
  int Query(int x, int y) {      // x != y; INF if disconnected
    access(x); access(y);
    return cost[x];
  }
  int AddEdge(int x, int y, int c) {   // x != y
    access(x); access(y);
    if (cost[x] > c) swap(cost[x], c);
    return c;
  }
};

Some notes:

• Vertices are $$$0, \ldots, n-1$$$, and $$$x$$$ must be different from $$$y$$$.
• Costs must be smaller than INF. For bigger costs, use long long and INF = 1e18.
• Equal costs are fine. If you want to know which edge was removed, use c * m + id as the cost (or pairs).

For example, this is how you keep the total cost of the MST:

long long total = 0;
int r = bt.AddEdge(x, y, c);
total += (r == INF) ? c : c - r;   // if the edge didn't enter, r == c

Main idea

We keep a rooted tree on the vertices. Each vertex $$$v$$$ stores its parent link[v] and the cost of the edge to its parent cost[v]. This tree is not the MST. We only need one property:

For any $$$u$$$ and $$$w$$$, the maximum cost on the path from $$$u$$$ to $$$w$$$ in our tree is the answer to Query(u, w).

At the start, all vertices are children of $$$0$$$ with cost INF. The root has cost INF + 1.

Let $$$p$$$ be the parent of $$$x$$$, and $$$g$$$ the parent of $$$p$$$. We call the edge of $$$x$$$ an up edge if cost[x] <= cost[p], and a down edge otherwise. We can do two moves:

• rotation of $$$x$$$ (if $$$x$$$ has an up edge): $$$x$$$ and $$$p$$$ swap places. Their costs also swap.
• skip of $$$x$$$ (if $$$x$$$ has a down edge): $$$x$$$ becomes a child of $$$g$$$. Its cost stays the same.

It's easy to check that these moves don't change any path maximum. You only need to look at the three pairs from $$$x$$$, $$$p$$$, $$$g$$$. Also, every vertex can always move up with one of the two moves.

Now suppose access(x) moves $$$x$$$ to the root. Then:

• After access(x) and access(y), $$$y$$$ is the root and $$$x$$$ is its child. So cost[x] is the answer to Query(x, y).
• In AddEdge, the new edge makes a cycle with only one tree edge: the one between $$$x$$$ and $$$y$$$. We keep the cheaper of the two and return the other one. This is the swap.

So everything depends on how access moves $$$x$$$ up.

The access loop

The first idea is: rotate on an up edge, skip on a down edge. Sadly, this is linear per access on simple inputs. For example, a star accessed in order, or a path with decreasing costs. It's the same story as with splay trees: rotating $$$x$$$ to the root one step at a time is too slow, and the fix is to also look at the grandparent and split into more cases (zig-zig and zig-zag).

Our fix: on a down edge, first move $$$p$$$ up by one step, and then let $$$x$$$ skip over $$$p$$$. These are the four cases in the code:

• (A) $$$x$$$ has an up edge: rotate $$$x$$$.
• (B) $$$x$$$ and $$$p$$$ both have down edges: skip $$$p$$$, then skip $$$x$$$.
• (C) $$$x$$$ has a down edge, $$$p$$$ has an up edge, and cost[g] <= cost[x]: rotate $$$p$$$, then skip $$$x$$$.
• (D) like (C), but cost[g] > cost[x]: only skip $$$x$$$.

The check in (C) and (D) is there so that $$$x$$$ can still skip $$$p$$$ after $$$p$$$ moves. We need both (B) and (C). Without any one of them, there are inputs where an access takes linear time.

Performance

We'll show that an access takes $$$O(\log n)$$$ amortized. We use the same potential as for splay trees:

Here $$$s(v)$$$ is the size of the subtree of $$$v$$$, and all logs are base 2. The code doesn't need these sizes. We only use them in the proof.

The key observation is this. One iteration of the loop only changes $$$x$$$, $$$p$$$ and $$$g$$$. After it, the new parent of $$$x$$$ is a vertex we haven't touched yet. So during access(x), the parent and grandparent of $$$x$$$ are always two neighbours on the initial path from $$$x$$$ to the root. Also, their subtree sizes are the initial ones.

Now let's look at one iteration. There are two cases:

• The vertex that moves has a big part of its parent's subtree (at least $$$2/3$$$ for rotations, at least $$$1/2$$$ for skips). Then $$$\Phi$$$ goes down by at least $$$1$$$. This pays for the iteration.
• Otherwise, the subtree sizes on the initial path grow by a constant factor at this point. This can happen only $$$O(\log n)$$$ times. Because the sizes are the initial ones, the increases of $$$\Phi$$$ add up to at most $$$O(\log n)$$$ in total.

If we do the math carefully, an access with $$$W$$$ iterations gives

$$$\Phi$$$ starts at $$$\log n$$$ and is never negative, so each operation is $$$O(\log n)$$$ amortized.

What was wrong with the old version?

The old BottleneckTree used the same two moves. But its access was recursive. It first went up to the root. Then, on the way back, it rotated the parent of $$$x$$$ over all cheaper ancestors, and then let $$$x$$$ skip.

The problem is that the recursion already changed the ancestors of $$$x$$$ before $$$x$$$ moves. So the proof above doesn't work. And this really happens. Let $$$L \approx 1.15\sqrt n$$$ be even, and do this:

1. Add the star AddEdge(v, 0, v) for $$$v = 1, \ldots, n-1$$$.
2. Take this sequence of vertices: for $$$r = L-1, \ldots, 0$$$, all vertices equal to $$$r$$$ modulo $$$L$$$, in decreasing order. Then $$$1, 2, \ldots, n-1$$$. Query consecutive pairs from it.

After the first part of step 2, every vertex points $$$L$$$ positions below itself. In the second part, the tree looks the same before every access, just shifted by one. Every access walks on a path of length $$$3L/2$$$ and does about $$$L$$$ rotations. So it does at least $$$1.9\sqrt n$$$ work per query. The full proof is in the paper (it's long).

For $$$n = 2^{20}$$$, the old version takes 10.6 seconds on this input. The new one takes 25 ms.

Extra: it's actually a link-cut tree in disguise

You don't need this part to use the structure. But I think it's the coolest part.

Suppose the graph is connected and all costs are distinct. Look at the Kruskal reconstruction tree (KRT) of the MST. Its leaves are the vertices. Each MST edge is an internal node, which joins two components (in increasing order of cost).

• Each vertex $$$v$$$ (except the root) "owns" the KRT node of its edge.
• Each KRT node has exactly one leaf that owns nothing inside it. The child that contains this leaf is the preferred child. Just like in link-cut trees, this splits the KRT into preferred paths.
• link[v] is like a path-parent pointer. It points to some leaf in the correct preferred subtree. It points to the "correct" leaf exactly when $$$v$$$ has an up edge. So a down edge means the pointer is outdated.
• Each rotation changes exactly one preferred child. The (A) rotations during access(z) are exactly the preferred child changes of a link-cut tree access to $$$z$$$ on the KRT.
• Skips don't change preferred children. They only fix outdated pointers, a bit like path halving in DSU.

A link-cut tree needs to splay to find where to attach a path. Here, the pointer goes directly to a leaf. So changing a preferred child is just one swap and two pointer changes. The downside is that pointers can become outdated, and the skips fix them later. Kudos to Claude for this observation.

Benchmarks

Time in ms, for $$$n = 2^{20}$$$ and $$$4n$$$ edges (AMD EPYC, g++ -O3):

Conclusions

Don't trust "probably $$$O(\log n)$$$" comments in my code :).

Some open questions, if anyone is interested:

• Is there something this simple with $$$O(\log n)$$$ worst-case queries?
• Does it have properties like splay trees (sequential access, working set)?

Thanks

Big thanks to Rajarshi Basu. His January 2020 solution to Transport Rutier on infoarena had the first version of this structure. Trying to find its complexity is how all of this started.

You can test the code on Transport Rutier, or on some of the problems from not_amir's blog. Do you know other problems where this is useful? Let me know in the comments and I'll add them to the blog.