Dizin Gezintisi#10412

Dizin Gezintisi

1 saniye

128 megabayt

Kolay

Bessie adlı inek bilgisayarlar konusunda şaşırtıcı derecede bilgilidir. Ahırdaki bilgisayarında tüm değerli dosyalarını bir dizin sisteminde saklamaktadır, örneğin:

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

bessie adında tek bir üst düzey dizin vardır.

Bessie herhangi bir dizine geçebilir. Geçerli dizinden herhangi bir dosyaya, .. sembolünün üst dizini belirttiği göreli bir yol ile erişilebilir. Örneğin, Bessie folder2 dizinindeyse, dört dosyaya şu şekilde erişebilir:

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

Bessie, tüm dosyalara olan göreli yolların toplam uzunluğunun minimum olacağı bir dizin seçmek istiyor.

Giriş

İlk satır, toplam dosya ve dizin sayısını belirten $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) tam sayısını içerir. Her nesneye (dosya veya dizin) $1$ 'den $n$ 'ye kadar benzersiz bir tam sayı numarası atanmıştır; burada $1$ numarası üst düzey dizine karşılık gelir.

Sonraki $n$ satırın her biri bir nesneyi tanımlar. Satır, dosya veya dizin adıyla başlar. Ad yalnızca küçük Latin harflerinden (' $a$ ' – ' $z$ ') ve rakamlardan (' $0$ ' – ' $9$ ') oluşur ve uzunluğu $16$ karakteri geçmez. Addan sonra $m$ tam sayısı gelir. Eğer $m = 0$ m = 0 ise, nesne bir dosyadır. Eğer $m > 0$ m > 0 ise, nesne doğrudan $m$ adet dosya veya dizin içeren bir dizindir; bu durumda bu dizinde bulunan nesnelerin numaraları olan $m$ tam sayı takip eder.

Çıktı

Tüm dosyalara olan göreli yolların mümkün olan en küçük toplam uzunluğunu yazdırın. Bu değerin $32$ bitlik tam sayı türüne sığmayabileceğine dikkat edin.

Örnekler

folder1 dizininde bulunmak en uygunudur. Bu dizinden göreli yollar şu şekildedir:

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

Örnek 1