Skip to Content
CTRL K

Mootube

Análisis oficial (Java) 

Editorial

Como quitar aristas mediante DSU no es viable, necesitamos una forma de procesar las consultas de modo que solo unamos nodos.

Podemos ordenar las consultas de mayor a menor peso para procesarlas offline. De manera similar, ordenamos las aristas según el mismo orden.

En cada consulta, podemos agregar toda arista con un peso mayor o igual al peso de la consulta actual.

Devolvemos el tamaño de la componente conexa menos uno como el número de videos que se recomendarán a partir del consultado.

Implementación

#include <bits/stdc++.h>
 
using namespace std;
 
struct DSU {
	vector<int> e;
	void init(int n) { e = vector<int>(n, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); };
	bool sameSet(int x, int y) { return get(x) == get(y); };
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
 
bool cmp(const pair<int, pair<int, int>> &a, const pair<int, pair<int, int>> &b) {
	return a.second.second > b.second.second;
}
 
int main() {
	freopen("mootube.in", "r", stdin);
	freopen("mootube.out", "w", stdout);
 
	int n, q;
	cin >> n >> q;
	vector<pair<int, pair<int, int>>> edges(n - 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		edges[i] = make_pair(w, make_pair(u, v));
	}
	vector<pair<int, pair<int, int>>> queries(q);
	for (int i = 0; i < q; i++) {
		int v, k;
		cin >> k >> v;
		v--;
		queries[i] = make_pair(i, make_pair(v, k));
	}
	sort(queries.begin(), queries.end(), cmp);
	sort(edges.begin(), edges.end(), greater<pair<int, pair<int, int>>>());
 
	DSU dsu;
	dsu.init(n);
	vector<int> sol(q);
	int idx = 0;
	for (auto query : queries) {
		int v = query.second.first;
		int curK = query.second.second;
		while (idx < (int)edges.size() && edges[idx].first >= curK) {
			dsu.unite(edges[idx].second.first, edges[idx].second.second);
			idx++;
		}
		sol[query.first] = dsu.size(v) - 1;
	}
 
	for (auto x : sol) { cout << x << '\n'; }
}
Fundamentos