ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Марсианская армия

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Марсиане много веков назад перешли на использование в военных действиях огромных человекоподобных роботов. В ходе нынешней кампании по завоеванию Луны вся марсианская армия размещается в штабе на Марсе, при этом каждый военный управляет из штаба по интернету действиями своего робота. В марсианской армии поддерживается строгая иерархия — у каждого военного, кроме генерала (генерал в армии всего один), есть непосредственный командир. По марсианскому уставу разрешено только общение командира с непосредственным подчинённым. Такое общение происходит по локальной сети штаба. Каждый военный имеет в штабе собственный компьютер; компьютеры пронумерованы числами от 1 до N, где N — численность марсианской армии. С давних пор повелось, что компьютер подчинённого имеет номер строго больше компьютера командира. Военные, кроме номера компьютера, характеризуются своей надёжностью — действительным числом: владелец компьютера i имеет надёжность Ai. Все на Марсе знают, что надёжность генерала равна 1, а надёжность рядовых (рядовые и только они на Марсе не имеют подчинённых) равна 0.
Наивно думать, что траффик внутри сети штаба ни во что не обходится военным. За каждый мегабайт траффика между i-м компьютером и компьютером командира владельца i-го компьютера главный марсианский провайдер требует плату в Ci золотых. Ситуацию осложняет то, что объём траффика между любой парой компьютеров в штабе является государственной тайной, и даже провайдеру он неизвестен. Провайдер поступает следующим образом: раз в месяц он присылает счёт, а военные сами вписывают в него траффик за месяц — неотрицательное число мегабайт. Пусть командир и подчинённый имеют компьютеры с номерами i и k соответственно. По договору с провайдером траффик по счёту между компьютерами i и k не должен быть меньше AiAk. В начале нового месяца представителям провайдера известна иерархия чинов в марсианской армии и цены за мегабайт траффика, однако неизвестны Ai всех чинов, кроме генерала и рядовых, и уж, конечно, неизвестны заранее те суммы в мегабайтах, которые военные впишут в счёт. Хотелось бы знать, какое гарантированное количество золотых может получить провайдер.

Исходные данные

В первой строке записано целое число 2 ≤ N ≤ 100000 — численность армии. В следующих N–1 строках расположены пары целых чисел Ki, Ci — номер компьютера командира владельца i-го компьютера и стоимость мегабайта траффика между компьютерами i и Ki. 1 ≤ Ki < iN, 0 ≤ Ci ≤ 1000.

Результат

Выведите действительное число — минимальную сумму в золотых, которую может гарантировать себе провайдер. Число должно содержать ровно 2 знака после десятичной точки.

Пример

исходные данныерезультат
7
1 10
2 5
2 3
3 1
3 2
3 3
8.00
Автор задачи: Александр Ипатов
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1472. Марсианская армия