Recorrido de directorios#10412

Recorrido de directorios

1 segundo

128 megabytes

Fácil

La vaca Bessie sabe sorprendentemente bien de computadoras. En su computadora del establo, guarda todos sus archivos importantes en un sistema de directorios, por ejemplo:

bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

Existe un único directorio de nivel superior, que se llama bessie.

Bessie puede situarse en cualquier directorio. Desde el directorio actual, se puede acceder a cualquier archivo mediante una ruta relativa, en la cual el símbolo .. denota el directorio padre. Por ejemplo, si Bessie se encuentra en el directorio folder2, puede acceder a los cuatro archivos de la siguiente manera:

../file1
file2
../../folder3/file3
../../file4

Bessie quiere elegir un directorio desde el cual la longitud total de las rutas relativas a todos los archivos sea mínima.

Entrada

La primera línea contiene un número entero $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — la cantidad total de archivos y directorios. A cada objeto (archivo o directorio) se le asigna un número entero único del $1$ al $n$ , donde el número $1$ corresponde al directorio de nivel superior.

Cada una de las siguientes $n$ líneas describe un objeto. La línea comienza con el nombre del archivo o directorio. El nombre está compuesto únicamente por letras latinas minúsculas (' $a$ ' – ' $z$ ') y dígitos (' $0$ ' – ' $9$ '), y su longitud no supera los $16$ caracteres. Después del nombre sigue un número entero $m$ . Si $m = 0$ m = 0, el objeto es un archivo. Si $m > 0$ m > 0, el objeto es un directorio que contiene directamente $m$ archivos o directorios; en ese caso, a continuación aparecen $m$ números enteros — los números de los objetos contenidos en ese directorio.

Salida

Muestre la longitud total mínima posible de las rutas relativas a todos los archivos. Tenga en cuenta que este valor puede no caber en un tipo entero de $32$ bits.

Ejemplos

Lo óptimo es situarse en el directorio folder1. Desde este directorio, las rutas relativas tienen la siguiente forma:

file1
folder2/file2
../folder3/file3
../file4

Ejemplo 1