Обхід каталогу#10412

Обхід каталогу

1 секунда

128 мегабайтів

Легка

Корова Бессі напрочуд добре розбирається в комп'ютерах. На своєму комп'ютері в сараї вона зберігає всі свої цінні файли в системі каталогів, наприклад:

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

Існує єдиний каталог верхнього рівня, який називається bessie.

Бессі може перейти в будь-який каталог. З поточного каталогу до будь-якого файлу можна звернутися за відносним шляхом, у якому символ .. позначає батьківський каталог. Наприклад, якщо Бессі знаходиться в каталозі folder2, вона може звернутися до чотирьох файлів наступним чином:

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

Бессі хоче обрати каталог, з якого сумарна довжина відносних шляхів до всіх файлів буде мінімальною.

Вхідні дані

Перший рядок містить ціле число $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) — загальну кількість файлів і каталогів. Кожному об'єкту (файлу чи каталогу) присвоєно унікальний цілочисельний номер від $1$ до $n$ , при цьому номер $1$ відповідає каталогу верхнього рівня.

Кожен із наступних $n$ рядків описує один об'єкт. Рядок починається з імені файлу або каталогу. Ім'я складається лише зі малих латинських літер (' $a$ ' – ' $z$ ') та цифр (' $0$ ' – ' $9$ '), а його довжина не перевищує $16$ символів. За ім'ям слідує ціле число $m$ . Якщо $m = 0$ m = 0, то об'єкт є файлом. Якщо $m > 0$ m > 0, то об'єкт є каталогом, який безпосередньо містить $m$ файлів або каталогів; у цьому випадку далі йдуть $m$ цілих чисел — номери об'єктів, що знаходяться в цьому каталозі.

Вихідні дані

Виведіть мінімально можливу сумарну довжину відносних шляхів до всіх файлів. Зверніть увагу, що це значення може не поміститися в $32$ -бітний цілий тип.

Приклади

Оптимально знаходитися в каталозі folder1. З цього каталогу відносні шляхи мають наступний вигляд:

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

Приклад 1