New Roads Queries

Explicación

Si construimos un grafo donde las aristas tienen pesos iguales al momento en que se agregan, el problema se reduce a hallar de forma eficiente el camino con la arista máxima mínima para cada consulta.

Consideremos una sola consulta entre los nodos $u, v$ . Una forma de abordarlo es ordenar los pesos de las aristas de menor a mayor, y luego agregar aristas de a una hasta que $u$ y $v$ estén conectados. Si usamos un Union-Find / conjuntos disjuntos (DSU), la complejidad temporal por consulta es $\mathcal{O}(m \cdot \alpha(n))$ , que es demasiado lenta.

Sin embargo, esto sugiere una solución más rápida. Notar que nuestro enfoque lento tiene muchas similitudes con el algoritmo de Kruskal para MST, lo que implica que el camino entre $u$ y $v$ en cualquier árbol de expansión mínima minimizará el peso de la arista máxima. Para una demostración más formal, ver aquí .

Lo único que queda es consultar de forma eficiente la arista máxima en un camino de un árbol. Una forma de hacerlo es con binary jumping.

Implementación

Complejidad temporal: $\mathcal{O}(m \cdot \alpha(n) + n\log n)$

C++


#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 2e5 + 1;
const int LOGN = 18;  // log de MAXN en base 2
 
// Clase DSU simple con fusión small-to-large
template <size_t N> struct UnionFind {
	int par[N], sze[N], max_size;
 
	UnionFind(int n = N) { init(n); }
 
	void init(int n = N) {
		iota(par, par + n, 0);
		fill(sze, sze + n, 1);
		max_size = 1;
	}
 
	int find(int a) {
		if (a == par[a]) return a;
		return par[a] = find(par[a]);
	}
 
	bool merge(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return 0;
 
		if (sze[a] > sze[b]) {
			par[b] = a;
			sze[a] += sze[b];
			max_size = max(max_size, sze[a]);
		} else {
			par[a] = b;
			sze[b] += sze[a];
			max_size = max(max_size, sze[b]);
		}
		return 1;
	}
 
	int size(int a) { return sze[find(a)]; }
};
 
int N, M, Q;
vector<pair<int, int>> G[MAXN];
UnionFind<MAXN> dsu;
 
namespace LCA {
int dep[MAXN], par[MAXN][LOGN], val[MAXN][LOGN];
 
void dfs_init(int u, int p, int d) {
	dep[u] = d;
	par[u][0] = p;
	for (auto [v, w] : G[u])
		if (p != v) {
			val[v][0] = w;
			dfs_init(v, u, d + 1);
		}
}
 
void init() {
	memset(dep, -1, sizeof(dep));
	memset(par, 0, sizeof(par));
	memset(val, 0, sizeof(val));
 
	for (int i = 1; i <= N; i++)
		if (dep[i] == -1) dfs_init(i, i, 0);
	for (int k = 1; k < LOGN; k++)
		for (int i = 1; i <= N; i++) {
			par[i][k] = par[par[i][k - 1]][k - 1];
			val[i][k] = max(val[i][k - 1], val[par[i][k - 1]][k - 1]);
		}
}
 
int query(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
 
	// llevar a y b a la misma profundidad
	int ans = 0;
	for (int d = LOGN - 1; d >= 0; d--)
		if (dep[b] - (1 << d) >= dep[a]) {
			ans = max(ans, val[b][d]);
			b = par[b][d];
		}
 
	if (a == b) return ans;
 
	for (int d = LOGN - 1; d >= 0; d--)
		if (par[a][d] != par[b][d]) {
			ans = max(ans, val[a][d]);
			a = par[a][d];
			ans = max(ans, val[b][d]);
			b = par[b][d];
		}
	if (par[a][0] != par[b][0]) return -1;
	ans = max(ans, val[a][0]);
	ans = max(ans, val[b][0]);
 
	return ans;
}
}  // namespace LCA
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	dsu.init();
 
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; i++) {
		int u, v;
		cin >> u >> v;
		if (dsu.merge(u, v)) {
			G[u].emplace_back(v, i);
			G[v].emplace_back(u, i);
		}
	}
 
	LCA::init();
 
	while (Q--) {
		int u, v;
		cin >> u >> v;
		cout << LCA::query(u, v) << '\n';
	}
}