Hello Codeforces!↵
↵
Some of you might know `BottleneckTree.h` from [my KACTL fork](https://github.com/bicsi/kactl/blob/master/content/graph/BottleneckTree.h) (although it's a little obscure for an ICPC notebook; oh well).Adrian Budău[user:freak93,2026-11-05] 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[user:RestingRajarshi,2026-11-05] (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](https://arxiv.org/abs/2611.05713). 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](https://codeforces.me/blog/entry/130107) by [user:not_amir,2026-11-05] 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↵
↵
```cpp↵
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:↵
↵
```cpp↵
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:↵
↵
$$\Phi = \sum_v \log s(v)$$↵
↵
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↵
↵
$$W + 2\Delta\Phi \le 3\log_{3/2} n + 5\log n < 10.13\log n$$↵
↵
$\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`):↵
↵
| input | new | old | link-cut tree |↵
|---|---|---|---|↵
| random edges, random order | 1065 | 2268 | 12748 |↵
| grid, local order | 367 | 618 | 3579 |↵
| band, local order | 198 | 299 | 2136 |↵
| the bad input above | 24.9 | 10642 | 398 |↵
↵
### 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 toRajarshi Basu[user:RestingRajarshi,2026-11-05]. His January 2020 solution to [Transport Rutier](https://infoarena.ro/problema/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](https://infoarena.ro/problema/rutier), or on some of the problems from [not_amir's blog](https://codeforces.me/blog/entry/130107). Do you know other problems where this is useful? Let me know in the comments and I'll add them to the blog.
↵
Some of you might know `BottleneckTree.h` from [my KACTL fork](https://github.com/bicsi/kactl/blob/master/content/graph/BottleneckTree.h) (although it's a little obscure for an ICPC notebook; oh well).
↵
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](https://arxiv.org/abs/2611.05713). 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](https://codeforces.me/blog/entry/130107) by [user:not_amir,2026-11-05] 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↵
↵
```cpp↵
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:↵
↵
```cpp↵
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:↵
↵
$$\Phi = \sum_v \log s(v)$$↵
↵
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↵
↵
$$W + 2\Delta\Phi \le 3\log_{3/2} n + 5\log n < 10.13\log n$$↵
↵
$\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`):↵
↵
| input | new | old | link-cut tree |↵
|---|---|---|---|↵
| random edges, random order | 1065 | 2268 | 12748 |↵
| grid, local order | 367 | 618 | 3579 |↵
| band, local order | 198 | 299 | 2136 |↵
| the bad input above | 24.9 | 10642 | 398 |↵
↵
### 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
↵
You can test the code on [Transport Rutier](https://infoarena.ro/problema/rutier), or on some of the problems from [not_amir's blog](https://codeforces.me/blog/entry/130107). Do you know other problems where this is useful? Let me know in the comments and I'll add them to the blog.
