Canicas en el árbol |
Tu tarea es mover las canicas de manera que cada caja contenga exactamente una canica. Esto se hace con una serie de movimientos, donde cada movimiento consiste en mover una canica a una caja adyacente (es decir, a un nodo hijo o padre). ¿Cuál es el número mínimo de movimientos para conseguir el objetivo?
La entrada puede contener varios casos de prueba. Cada caso empieza con el número de nodos, n, seguido de n líneas. Cada línea contiene al menos 3 números que son: v el número del vértice, el número de canicas colocadas inicialmente en ese vértice, seguido de un número d que indica el número de hijos de v, y finalmente vienen d números con las identidades de los hijos de v.
La entrada acaba con un caso donde n = 0. Este caso no debe ser procesado.
Para cada caso de entrada, la salida debe ser el menor número de movimientos de canicas para colocar una canica en cada nodo del árbol.
9 1 2 3 2 3 4 2 1 0 3 0 2 5 6 4 1 3 7 8 9 5 3 0 6 0 0 7 0 0 8 2 0 9 0 0 9 1 0 3 2 3 4 2 0 0 3 0 2 5 6 4 9 3 7 8 9 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 9 1 0 3 2 3 4 2 9 0 3 0 2 5 6 4 0 3 7 8 9 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 0
7 14 20