Clock Tree

Explicación

Podemos construir un grafo con las habitaciones como nodos y los pasillos como aristas. Consideremos un caso simple: hay 2 nodos en el grafo y una arista. Bessie puede empezar en una de las habitaciones, ir a su vecina, adelantar el reloj, volver y adelantar el reloj de la habitación inicial. Durante este proceso de ir y volver, nótese que la diferencia entre las lecturas de los dos relojes solo puede cambiar en 1. Si las lecturas iniciales de los relojes difieren en uno, Bessie puede empezar en la habitación con la lectura mayor e ir y volver hasta que ambos relojes marquen 12. Si las lecturas iniciales de los relojes difieren en más de uno, es imposible que Bessie haga que ambos relojes marquen 12.

Si hay más nodos, podemos tratarlo de forma similar al caso de dos nodos considerando los dos grupos de una partición bipartita. Como todos los árboles son grafos bipartitos, esta partición siempre existe.

La primera vez que Bessie visita un nodo vecino, la suma de los relojes del primer grupo aumenta en 1. Luego Bessie visita otro nodo vecino y la suma de los relojes del segundo grupo aumenta en 1. Como ambas sumas aumentan en uno, la diferencia entre las sumas no cambia. Este proceso se repite hasta que todos los relojes llegan a 12.

Podemos comprobar la diferencia inicial de las sumas entre los dos grupos (módulo 12) para hallar los números finales de los relojes, donde definimos $\texttt{group0}$ y $\texttt{group1}$ como las sumas de los relojes de cada uno de los dos grupos de la partición bipartita.

Si $\texttt{group0}$ es igual a $\texttt{group1}$ (módulo 12), Bessie puede empezar en cualquier nodo.
Si $\texttt{group0}$ es 1 menor que $\texttt{group1}$ (módulo 12), Bessie puede empezar en cualquier nodo de $\texttt{group1}$ .
Si $\texttt{group1}$ es 1 menor que $\texttt{group0}$ (módulo 12), Bessie puede empezar en cualquier nodo de $\texttt{group0}$ .
Si $\texttt{group0}$ y $\texttt{group1}$ difieren en al menos 2 (módulo 12), no hay forma de hacer que todos los relojes marquen 12.

Solución en video

Video de YouTube (vMA54A2AT0I)

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int N;
vector<int> edges[100000];
int A[100000];
int sum0, sum1, nodes0, nodes1;
 
void dfs(int i, int color, int par) {
	// actualizar color/suma
	if (color == 0) {
		nodes0++;
		sum0 += A[i];
	} else {
		nodes1++;
		sum1 += A[i];
	}
 
	for (int j : edges[i]) {
		if (j != par) {
			// intercambiar colores para el hijo
			dfs(j, 1 - color, i);
		}
	}
}
 
int main() {
	freopen("clocktree.in", "r", stdin);
	freopen("clocktree.out", "w", stdout);
 
	cin >> N;
 
	for (int i = 0; i < N; i++) { cin >> A[i]; }
 
	for (int i = 1; i < N; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
 
	dfs(0, 0, -1);
 
	// el mismo módulo significa que se puede empezar en cualquier lado
	if ((sum0 % 12) == (sum1 % 12)) {
		cout << N;
	}
	// si group0 es 1 menor que group1, debemos empezar en group1
	else if ((sum0 + 1) % 12 == (sum1 % 12)) {
		cout << nodes1;
	}
	// si group1 es 1 menor que group0, debemos empezar en group0
	else if ((sum0 % 12) == ((sum1 + 1) % 12)) {
		cout << nodes0;
	}
	// no hay forma de hacer que todos los relojes marquen 12
	else {
		cout << 0;
	}
}


public class ClockTree {
	static int[] clocks;
	static List<List<Integer>> adj;
	static int sum0 = 0, sum1 = 0, nodes0 = 0, nodes1 = 0;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("clocktree");
 
		int n = io.nextInt();
		clocks = new int[n];
		adj = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			clocks[i] = io.nextInt();
			adj.add(new ArrayList<>());
		}
		for (int i = 0; i < n - 1; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj.get(a).add(b);
			adj.get(b).add(a);
		}
 
		dfs(0, 0, -1);
 
		// el mismo módulo significa que se puede empezar en cualquier lado
		if ((sum0 % 12) == (sum1 % 12)) {
			io.println(n);
		}
		// si group0 es 1 menor que group1, debemos empezar en group1
		else if ((sum0 + 1) % 12 == (sum1 % 12)) {
			io.println(nodes1);
		}
		// si group1 es 1 menor que group0, debemos empezar en group0
		else if ((sum0 % 12) == ((sum1 + 1) % 12)) {
			io.println(nodes0);
		}
		// no hay forma de hacer que todos los relojes marquen 12
		else {
			io.println(0);
		}
		io.close();
	}
 
	static void dfs(int i, int color, int par) {
		// actualizar color/suma
		if (color == 0) {
			nodes0++;
			sum0 += clocks[i];
		} else {
			nodes1++;
			sum1 += clocks[i];
		}
 
		for (int j : adj.get(i)) {
			if (j != par) {
				// intercambiar colores para el hijo
				dfs(j, 1 - color, i);
			}
		}
	}
 
	// CodeSnip{Kattio}
}


with open("clocktree.in", "r") as reader:
	n = int(reader.readline())
	clocks = list(map(int, reader.readline().split()))
 
	edges = [list() for _ in range(n)]
	for _ in range(n - 1):
		a, b = map(lambda s: int(s) - 1, reader.readline().split())
		edges[a].append(b)
		edges[b].append(a)
 
# cantidad de nodos y sumas de group0 y group1
nodes = [0, 0]
sums = [0, 0]
 
 
def dfs(i: int, parent: int, color: bool):
	# actualizar color/suma
	if color:
		nodes[0] += 1
		sums[0] += clocks[i]
	else:
		nodes[1] += 1
		sums[1] += clocks[i]
 
	for j in edges[i]:
		if j != parent:
			dfs(j, i, not color)  # intercambiar colores para el hijo
 
 
dfs(i=0, parent=-1, color=True)
 
with open("clocktree.out", "w") as writer:
	# el mismo módulo significa que se puede empezar en cualquier lado
	if sums[0] % 12 == sums[1] % 12:
		print(n, file=writer)
 
	# si sums0 es 1 menor que sums1, debemos empezar en cualquier nodo de group1
	elif (sums[0] + 1) % 12 == (sums[1] % 12):
		print(nodes[1], file=writer)
 
	# si sums1 es 1 menor que sums0, debemos empezar en cualquier nodo de group0
	elif sums[0] % 12 == (sums[1] + 1) % 12:
		print(nodes[0], file=writer)
 
	# en caso contrario, no hay forma de hacer que todos los relojes marquen 12
	else:
		print(0, file=writer)