CSES - New Roads Queries

If we construct a graph where edges have weights equal to the time they are added, the problem boils down to efficiently finding the path with the minimum maximum edge for each query.

Let's consider a single query between nodes $u, v$. One way of approaching this is to sort the edge weights from smallest to largest, and then add edges one by one until $u$ and $v$ are connected. If we use a disjoint set union, the time complexity for each query is $\mathcal{O}(m \cdot \alpha(n))$, which is too slow.

However, this hints at a faster solution. Note that our slow approach bears many similarities with Kruskal's MST algorithm, which implies that the path between $u$ and $v$ on any minimum spanning tree will minimize the maximum edge weight. For a more formal proof, see here.

All that is left to do is to efficiently query for the maximum edge on a tree path. One way to do this is with binary jumping.

Implementation

Time Complexity: $\mathcal{O}(m \cdot \alpha(n) + n\log n)$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;
const int LOGN = 18;  // log of MAXN base 2

// Simple DSU class with Small to Large merging
template <size_t N> struct UnionFind {
	int par[N], sze[N], max_size;