Attraversamento di cartelle#10412

Attraversamento di cartelle

1 secondo

128 megabyte

Facile

La mucca Bessie è sorprendentemente esperta di computer. Sul suo computer nel fienile conserva tutti i suoi file preziosi in un sistema di cartelle, ad esempio:

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

Esiste un'unica cartella di livello superiore, che si chiama bessie.

Bessie può spostarsi in qualsiasi cartella. Dalla cartella corrente, qualsiasi file può essere raggiunto tramite un percorso relativo, in cui il simbolo .. indica la cartella superiore. Ad esempio, se Bessie si trova nella cartella folder2, può accedere ai quattro file nel modo seguente:

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

Bessie vuole scegliere una cartella dalla quale la lunghezza totale dei percorsi relativi a tutti i file sia minima.

Input

La prima riga contiene un numero intero $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — il numero totale di file e cartelle. A ogni oggetto (file o cartella) è assegnato un numero intero unico da $1$ a $n$ , dove il numero $1$ corrisponde alla cartella di livello superiore.

Ciascuna delle successive $n$ righe descrive un oggetto. La riga inizia con il nome di un file o di una cartella. Il nome è composto solo da lettere latine minuscole (' $a$ ' – ' $z$ ') e cifre (' $0$ ' – ' $9$ '), e la sua lunghezza non supera i $16$ caratteri. Dopo il nome segue un numero intero $m$ . Se $m = 0$ m = 0, l'oggetto è un file. Se $m > 0$ m \gt 0, l'oggetto è una cartella che contiene direttamente $m$ file o cartelle; in questo caso seguono $m$ numeri interi — i numeri degli oggetti contenuti in questa cartella.

Output

Stampare la lunghezza totale minima possibile dei percorsi relativi a tutti i file. Si noti che questo valore potrebbe non entrare in un tipo intero a 32 bit.

Esempi

È ottimale trovarsi nella cartella folder1. Da questa cartella i percorsi relativi hanno la seguente forma:

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

Esempio 1