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 
hijos, para cada hijo 
sea 
el subárbol de , 
el número de hojas de , y 
el peso del árbol obtenido de realizar el procedimiento del párrafo anterior a . Si todas las 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 continúe estando balanceado. La única manera que le podemos restar peso a sería restarle la misma cantidad de peso a cada una de sus hojas. Entonces, a cada sólo podemos restarle peso en múltiplos de . Como queremos maximizar el peso del árbol resultante, necesitamos encontrar el número más grande 
tal que a todos los les podamos restar un múltiplo de su respectivo para obtener . Notemos también que es un múltiplo de porque los nodos internos del árbol no tienen peso. Si 
es el mínimo común múltiplo de todos los , entonces también es un múltiplo de . Entonces, el máximo posible es igual al múltiplo de más grande que sea menor o igual a todos los . Por lo tanto, el valor máximo obtenible del árbol completo es igual a 
. 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 
, y si seguimos restando continuará balanceado.
De esta observación podemos obtener la solución para cualquier árbol. Reusando la notación del párrafo anterior, es la cantidad de hijos de la raíz, el subárbol del ésimo hijo, y el peso del árbol obtenido de realizar recursivamente el procedimiento de éste párrafo a (o el del anterior si tiene 2 niveles). Ahora es igual a lo mínimo que le podemos restar a y que continúe balanceado. El análisis del párrafo anterior también es correcto para la nueva definición de y .
El código siguiente implementa esta solución: