Game On Tree

Explicación

Como el juego del problema se parece a Nim, intentemos usar números de Sprague-Grundy.

Para resolver el problema, para una cierta raíz con subárboles $s_1, s_2, ..., s_k$ , podemos intentar convertir todos estos subárboles en una pila de algún tamaño. Luego, haciendo XOR de todos estos tamaños de pila (como en Nim), podemos saber si ganamos o perdemos en este árbol.

Para calcular el tamaño de la pila de un subárbol, podemos resolver el problema de forma recursiva. Para un subárbol con $1$ nodo, el tamaño de la pila será $0$ porque no hay aristas que se puedan eliminar.

Si el valor de Grundy de la raíz es positivo, entonces Alice gana; si el valor de Grundy de la raíz es $0$ , gana Bob.

Observemos que cuando obtenemos los números de Grundy de cada subárbol hay que sumar $1$ a todos ellos antes de hacer XOR. Esto es porque el tamaño de cada pila aumenta en $1$ al considerar la arista desde la raíz de $s_i$ hasta la raíz de todo el árbol.

Por ejemplo, consideremos el árbol:

Para los subárboles enraizados en $2$ y $3$ , los valores de Grundy serán $0$ . Para el árbol enraizado en $1$ , el valor de Grundy será $(1 + 0) \oplus (1 + 0) = 0$ . Esto tiene sentido porque, cualquiera sea la arista que elija Alice, Bob puede elegir la otra, dejando a Alice sin arista que eliminar, y ella pierde.

Implementación

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

C++Python


#include <functional>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<vector<int>> g(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
 
	function<int(int, int)> dfs = [&](int u, int p) {
		int sg = 0;
		for (int v : g[u]) {
			if (v ^ p) {
				/*
				 * Sumamos 1 porque la arista de u a v aumenta el tamaño de
				 * cada pila en 1
				 */
				sg ^= dfs(v, u) + 1;
			}
		}
		return sg;
	};
 
	cout << (dfs(1, 0) ? "Alice" : "Bob") << endl;
}


import sys, pypyjit
 
# mejora el rendimiento de funciones muy recursivas al permitir que PyPy omita el unrolling
pypyjit.set_param("max_unroll_recursion=-1")
 
sys.setrecursionlimit(10**7)
 
 
def dfs(u: int, p: int) -> int:
	sg = 0
	for v in g[u]:
		if v != p:
			# Sumamos 1 porque la arista de u a v aumenta el tamaño de
			# cada pila en 1
			sg ^= dfs(v, u) + 1
 
	return sg
 
 
n = int(input())
g = [[] for _ in range(n + 1)]
 
for _ in range(n - 1):
	u, v = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
 
print("Alice" if dfs(1, 0) else "Bob")