Mergers

Explicación

Primero, notemos que si existe una ciudad del estado $B$ que se encuentra entre dos ciudades del estado $A$ , entonces los estados $A$ y $B$ necesariamente deben pertenecer al mismo grupo. Así, podemos fusionar los estados $A$ y $B$ en un solo estado.

Si repetimos esta fusión hasta que no se pueda más, terminaremos con un árbol en el que cada nodo representa un conjunto disjunto de estados. Por lo tanto, solo necesitamos resolver el problema bajo el supuesto de que cada estado contiene exactamente una ciudad.

Notemos que el único caso en el que no se requieren fusiones es cuando el árbol resultante consiste en un solo nodo. En caso contrario, podemos tomar cualquier hoja del árbol y ponerla sola en el Grupo X, y todos los demás nodos en el Grupo Y.

400|center

Ahora, consideremos un grafo estrella con $n$ hojas. ¿Cuál es la cantidad mínima de fusiones para reducir esta estrella a un solo nodo? Notemos que en una sola fusión, podemos eliminar a lo sumo dos hojas fusionando dos hojas: por lo tanto, la cantidad total de fusiones requeridas es $\lceil \frac{n}{2} \rceil$ .

Para terminar, notemos que esta fórmula de hecho se generaliza: en particular, para cualquier árbol en el que todas las ciudades pertenecen a estados distintos, la cantidad total de fusiones requeridas es $\lceil \frac{\text{\# of leaves}}{2} \rceil$ . Para mostrarlo, consideremos enraizar el árbol en el centroide de hojas, de modo que ningún subárbol contenga estrictamente más de la mitad de las hojas. Afirmamos que en cada fusión, podemos elegir dos hojas que pertenezcan a subárboles distintos; por lo tanto, todas las hojas se unirán a la raíz.

El diagrama de la izquierda muestra el árbol correctamente enraizado en el centroide de hojas. El diagrama de la derecha muestra que si no emparejamos según este centroide, todas las hojas podrían no unirse después de $\lceil \frac{\text{\# of leaves}}{2} \rceil$ fusiones.

Demostración de que el centroide de hojas existe

La demostración es esencialmente la misma que la de que existe un centroide normal de un árbol. A saber, para el caso de un centroide normal de un árbol, solo necesitamos escribir el algoritmo de búsqueda del centroide y demostrar que termina. Luego, notemos que la misma demostración vale cuando a cada nodo se le puede asignar un peso; por lo tanto, podemos hallar nuestro centroide de hojas deseado asignando a las hojas peso 1 y a todos los demás nodos peso 0.

Demostración de que existe un emparejamiento

Ahora queremos demostrar que, cuando el árbol está enraizado en el centroide de hojas, podemos partir las hojas en pares de modo que ningún par contenga dos hojas del mismo subárbol. Esto se reduce a mostrar lo siguiente:

Tengo hojas de $n$ tipos distintos. Si tengo $c_i$ hojas del $i$ -ésimo tipo, y quiero partir estas hojas en pares de modo que ningún par contenga dos hojas del mismo tipo, esto es posible sii $2 \cdot \max c_i \leq \sum c_i$ .

Esto se puede demostrar por inducción. Sin pérdida de generalidad, sea $c_1 = \max c_i$ .

Si la desigualdad se cumple con igualdad, es decir $c_1 = c_2 + c_3 + ... + c_n$ , podemos formar pares tales que cada par contenga exactamente una hoja de tipo 1.
En caso contrario, podemos emparejar una hoja de tipo 1 con una hoja de cualquier otro tipo, y la desigualdad seguirá valiendo.

Fusión de componentes que se intersectan

Resta realizar rápido los primeros pasos de fusionar estados $A$ y $B$ que se intersectan. Para esto, podemos definir un procedimiento merge(tree, root) que halla todas las componentes completadas que yacen estrictamente dentro de tree, y luego devuelve la componente (potencialmente incompleta) adjunta a la raíz.

Notemos que la componente devuelta (marcada en rojo) está incompleta porque todavía existe una ciudad en el estado 2 que yace fuera de este árbol.

Ahora, merge(tree, root) se puede implementar recursivamente de la siguiente forma:

Llamar a merge(subtree, child) para cada hijo de root y agregar cada nodo de la componente devuelta a un conjunto $C$ .
Agregar root a $C$ , y luego comprobar si $C$ forma una componente completa.
Si $C$ está completa, devolver $\emptyset$ ; en caso contrario, devolver $C$ .

500|center

Aquí, $C$ está incompleta porque contiene algunas pero no todas las ciudades del estado 1.

Para terminar, notemos que “comprobar si $C$ forma una componente completa” se hace fácilmente con hashing XOR. Para más detalles, consultar mi código + comentarios de abajo.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int main() {
	int n, k;
	cin >> n >> k;
	auto g = vector(n + 1, vector<int>());
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	// sums[i]: el XOR de todos los hashes de las ciudades del estado i
	// lst[i]: guarda una ciudad que pertenece al estado i (si hay alguna)
	vector<int> sums(k + 1), val(n + 1), s(n + 1), lst(k + 1);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		sums[s[i]] ^= (val[i] = rng());
		lst[s[i]] = i;
	}
	// hacemos esto para que los hashes de todas las ciudades de un estado dado den XOR 0
	for (int i = 1; i <= k; i++)
		if (lst[i]) val[lst[i]] ^= sums[i];
	int leaves = 0;
	// implementación de merge(tree, root)
	// devuelve [grado de C, XOR de C] donde C es la componente de la raíz potencialmente incompleta
	[&](this auto dfs, int x, int p) -> array<int, 2> {
		int deg = 0, cur = val[x];
		for (int y : g[x])
			if (y != p) {
				auto [d, sm] = dfs(y, x);
				deg += d, cur ^= sm;
			}
		if (!cur && deg + (p > 0) == 1) ++leaves;
		return {cur ? deg : 1, cur};
	}(1, 0);
	cout << (leaves + 1) / 2 << "\n";
}