Skip to Content
CTRL K

2015 - Uzastopni

Explicación

El núcleo de este problema es verificar la restricción de “conjunto consecutivo” a lo largo de una estructura de árbol. Como cada grupo invitado debe ser un subárbol conexo enraizado en Petar, podemos plantear el problema como encontrar todos los rangos continuos de chistes [L,R][L, R] que se pueden formar con un subárbol válido.

La lógica central

El “truco” es reconocer que para que cualquier empleado uu satisfaga la regla consecutiva, su propio chiste VuV_u debe actuar como el puente entre los distintos rangos de chistes que proveen sus subordinados.

Si el empleado uu cuenta el chiste 5, solo puede formar un rango válido si sus subordinados colectivamente proveen rangos que “tocan” perfectamente el 5—por ejemplo, un subordinado que provee [3,4][3, 4] y otro que provee [6,7][6, 7]. Juntos, crean el conjunto sin huecos [3,7][3, 7].

Mantenemos dos bitsets para cada nodo x:

  • lans[x][v] = 1 si el subárbol enraizado en x puede cubrir todos los tipos de chiste desde v hasta joke[x]
  • rans[x][v] = 1 si el subárbol enraizado en x puede cubrir todos los tipos de chiste desde joke[x] hasta v - 1

Inicialmente, cada nodo siempre puede formar el intervalo trivial que contiene solo su propio chiste.

Construcción con DFS

Procesamos el árbol con un DFS en postorden.

Para un nodo x, después de procesar todos los hijos:

  1. Dividimos los hijos en dos grupos:
    • lo: hijos cuyo tipo de chiste es menor que joke[x]
    • hi: hijos cuyo tipo de chiste es mayor que joke[x]
  2. Para extender hacia la izquierda, procesamos lo en orden decreciente de tipo de chiste. Si la expansión izquierda actual de x se solapa con la expansión derecha de un hijo, podemos fusionarlos de forma segura.
  3. Para extender hacia la derecha, procesamos hi en orden creciente de tipo de chiste. Si la expansión derecha actual de x se solapa con la expansión izquierda de un hijo, también los fusionamos.

El ordenamiento garantiza que:

  • los tipos de chiste permanecen únicos,
  • no se introducen huecos,
  • y solo se forman conjuntos consecutivos válidos.

En la raíz (Petar), cualquier conjunto consecutivo válido se determina eligiendo:

  • un extremo izquierdo válido de lans[0], y
  • un extremo derecho válido de rans[0].

Así, el número total de conjuntos de chistes distintos que Petar puede ver es el producto del número de extremos izquierdos y derechos válidos en la raíz.

Implementación

Complejidad temporal: O(N⋅V/w)\mathcal{O}(N \cdot V / w)

 
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> child;
vector<int> joke;
vector<bitset<101>> lans, rans;
 
// BeginCodeSnip{DFS}
void dfs(int x) {
	vector<int> lo, hi;
 
	for (int y : child[x]) {
		dfs(y);
		if (joke[y] < joke[x]) lo.push_back(y);
		if (joke[y] > joke[x]) hi.push_back(y);
	}
 
	// Base case: interval containing only joke[x]
	lans[x][joke[x]] = 1;
	rans[x][joke[x] + 1] = 1;
 
	// Extend to smaller joke types
	sort(lo.begin(), lo.end(), [&](int a, int b) { return joke[a] > joke[b]; });
 
	for (int y : lo) {
		if ((lans[x] & rans[y]).any()) { lans[x] |= lans[y]; }
	}
 
	// Extend to larger joke types
	sort(hi.begin(), hi.end(), [&](int a, int b) { return joke[a] < joke[b]; });
 
	for (int y : hi) {
		if ((rans[x] & lans[y]).any()) { rans[x] |= rans[y]; }
	}
}
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int N;
	cin >> N;
 
	joke.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> joke[i];
		--joke[i];  // make joke types 0-based
	}
 
	child.assign(N, {});
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		child[a].push_back(b);
	}
 
	lans.assign(N, bitset<101>());
	rans.assign(N, bitset<101>());
 
	dfs(0);
 
	long long ans = 1LL * lans[0].count() * rans[0].count();
	cout << ans << "\n";
 
	return 0;
}
Fundamentos