Solución a "Mocha Hojas"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17 Autor: Freddy Román Cepeda Fuente: Alberto José Ramírez Valadez
Para simplificar el análisis, podemos notar que la respuesta que nos piden es igual al total de los pesos de las hojas del árbol menos el total de los pesos de las hojas del árbol ya balanceado. De ahora en adelante, trataremos el problema como si tuviéramos que conseguir este segundo valor, en vez del número de operaciones. Entonces queremos maximizar el peso total del árbol balanceado, para minimizar la cantidad de operaciones.
Consideremos el caso de un árbol con un solo nivel. Ya que sólo podemos restarle a los pesos de las hojas, evidentemente el peso máximo del árbol se alcanza cuando se emparejan todas las hojas al peso de la hoja con peso mínimo.
Ahora, consideremos un árbol con dos niveles. Si la raíz tiene $ k$ hijos, para cada hijo $ i$ sea $ h_i$ el subárbol de $ i$, $ b_i$ el número de hojas de $ h_i$, y $ c_i$ el peso del árbol obtenido de realizar el procedimiento del párrafo anterior a $ h_i$. Si todas las $ c_i$ son iguales, entonces nuestro árbol está balanceado. De lo contrario, debemos restar aún más para poder balancearlo. Sin embargo, también necesitamos que cada $ h_i$ continúe estando balanceado. La única manera que le podemos restar peso a $ h_i$ sería restarle la misma cantidad de peso a cada una de sus hojas. Entonces, a cada $ h_i$ sólo podemos restarle peso en múltiplos de $ b_i$. Como queremos maximizar el peso del árbol resultante, necesitamos encontrar el número más grande $ x$ tal que a todos los $ c_i$ les podamos restar un múltiplo de su respectivo $ b_i$ para obtener $ x$. Notemos también que $ c_i$ es un múltiplo de $ b_i$ porque los nodos internos del árbol no tienen peso. Si $ m$ es el mínimo común múltiplo de todos los $ b_i$, entonces $ x$ también es un múltiplo de $ m$. Entonces, el máximo $ x$ posible es igual al múltiplo de $ m$ más grande que sea menor o igual a todos los $ c_i$. Por lo tanto, el valor máximo obtenible del árbol completo es igual a $ kx$. Por último, si tuviéramos que restarle más peso a este árbol pero mantenerlo balanceado, es evidente que lo menos que podemos restar para mantenerlo balanceado es $ km$, y si seguimos restando $ km$ continuará balanceado.
De esta observación podemos obtener la solución para cualquier árbol. Reusando la notación del párrafo anterior, $ k$ es la cantidad de hijos de la raíz, $ h_i$ el subárbol del $ i$ésimo hijo, y $ c_i$ el peso del árbol obtenido de realizar recursivamente el procedimiento de éste párrafo a $ h_i$ (o el del anterior si $ h_i$ tiene 2 niveles). Ahora $ b_i$ es igual a lo mínimo que le podemos restar a $ h_i$ y que continúe balanceado. El análisis del párrafo anterior también es correcto para la nueva definición de $ b_i$ y $ c_i$.
El código siguiente implementa esta solución: