Hello, Codeforces. Recently I’ve been watching some educational contests, and I came across problem 609E - Minimum spanning tree for each edge. As we can see, it doesn’t have the “binary search” tag, but I found a nice solution using Kruskal’s algorithm together with parallel binary search. This is my AC submission 356579606.

First, I build the minimum spanning tree of the graph. Then, for every edge, I find the moment during Kruskal’s algorithm when the two endpoints of that edge are already connected. At that moment, if we added this edge instead of one of the edges chosen by Kruskal, we would create a cycle. Replacing the corresponding edge from the MST with this one produces another spanning tree with a slightly larger total cost — and that cost is exactly the answer for that edge. The correctness of this idea is very similar to the correctness proof of Kruskal’s algorithm.

So the only thing that remains is to find that “moment” for each edge. For a single edge, we could find it with a standard binary search, but each step requires rebuilding a DSU. This allows us to use parallel binary search, giving a complexity of O(m * log(n) * a(n)), where a(n) is Ackerman number of n, which is OK. For me this problem must have 'greedy' and 'binary search' tags too.