Skip to Content
CTRL K

2009 - Regions

Análisis oficial 

Pista #1

Consideremos precalcular todas las respuestas a consultas que involucran alguna región padre r1r_1.

Pista #2

Podemos responder todas las consultas en O(Slog⁡N)\mathcal{O}(S\log{N}), donde SS es el tamaño de la región padre r1r_1. ¿Cómo deberíamos elegir las regiones que precalculamos, dada esta información?

Respuesta a la Pista #2

Precalculamos la respuesta para todas las consultas que involucran regiones de tamaño mayor que N\sqrt{N}.

Explicación

Como se mencionó en las pistas, precalcularemos la respuesta para todas las regiones padre de tamaño mayor que N\sqrt{N}. Luego, respondemos las consultas o bien calculando la respuesta online o bien usando una respuesta precalculada.

Para precalcular todas las respuestas de una región padre dada, hacemos DFS sobre el árbol. Mientras recorremos el árbol hacia abajo, llevamos la cuenta de cuántas veces hemos visto un empleado que forma parte de esta región padre actual. Este número lleva la cuenta de las ocurrencias de la región padre como supervisor de la región de nuestro empleado actual. Con esta información, podemos guardar estas respuestas en un arreglo calc[r1][r2]calc[r_1][r_2], donde r1r_1 es nuestra región padre y r2r_2 es cualquier otra región. Notemos que, como solo precalculamos a lo sumo N\sqrt{N} valores de r1r_1, la complejidad espacial es O(NN)\mathcal{O}(N\sqrt{N}).

Para regiones padre de tamaño menor que N\sqrt{N}, respondemos las consultas online. Antes de responder consultas, ejecutamos un tour de Euler del árbol. Para cada nodo dentro de esta región padre actual, contamos la cantidad de nodos en la región hija. Como el subárbol de cada nodo contiene un rango de nodos (cuando se etiquetan por sus tiempos de recorrido del tour de Euler), podemos usar búsqueda binaria para contar la cantidad de tales nodos hijos.

Implementación

Complejidad temporal: O(NN+QNlog⁡N)\mathcal{O}(N\sqrt{N}+Q\sqrt{N}\log{N})

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, r, q;
	cin >> n >> r >> q;
	vector<int> region(n);
	cin >> region[0];
	region[0]--;
	vector<vector<int>> adj(n);
	for (int i = 1; i < n; i++) {
		int p, h;
		cin >> p >> h;
		p--, h--;
		adj[p].push_back(i);
		region[i] = h;
	}
 
	// Calculamos los índices del tour de Euler.
	vector<int> tin(n);
	vector<int> tout(n);
	vector<int> tin_node(n);  // tin[tin_node[i]] = i
	vector<vector<int>> comp(r);
	int timer = 0;
	function<void(int)> tour = [&](int u) -> void {
		tin[u] = timer++;
		tin_node[tin[u]] = u;
		comp[region[u]].push_back(tin[u]);
		for (int v : adj[u]) { tour(v); }
		tout[u] = timer;
	};
	tour(0);
 
	// Precalculamos la respuesta para regiones padre
	// con >= sqrt(n) miembros.
	const int BLOCK = sqrt(n);
	vector<vector<int>> calc;
	vector<int> region_id(r, -1);
	function<void(int, int, int)> dfs = [&](int u, int parent_region,
	                                        int parent_count) -> void {
		if (region[u] == parent_region) { parent_count++; }
		calc[region_id[parent_region]][region[u]] += parent_count;
		for (int v : adj[u]) { dfs(v, parent_region, parent_count); }
	};
 
	int current_id = 0;
	for (int i = 0; i < r; i++) {
		if ((int)comp[i].size() >= BLOCK) {
			region_id[i] = current_id++;
			calc.push_back(vector<int>(r));
			dfs(0, i, 0);
		}
	}
 
	// Respondemos las consultas, o bien con los valores precalculados
	// o bien usando tour de Euler + búsqueda binaria.
	for (int i = 0; i < q; i++) {
		int e1, e2;
		cin >> e1 >> e2;
		e1--, e2--;
		if ((int)comp[e1].size() >= BLOCK) {
			cout << calc[region_id[e1]][e2] << "\n";
		} else {
			int total = 0;
			for (int u : comp[e1]) {
				total +=
				    lower_bound(begin(comp[e2]), end(comp[e2]), tout[tin_node[u]]) -
				    lower_bound(begin(comp[e2]), end(comp[e2]), tin[tin_node[u]]);
			}
			cout << total << '\n';
		}
	}
}
Fundamentos