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

[b322730]

Марсиане много веков назад перешли на использование в военных действиях огромных человекоподобных роботов. В ходе нынешней кампании по завоеванию Луны вся марсианская армия размещается в штабе на Марсе, при этом каждый военный управляет из штаба по интернету действиями своего робота. В марсианской армии поддерживается строгая иерархия — у каждого военного, кроме генерала (генерал в армии всего один), есть непосредственный командир. По марсианскому уставу разрешено только общение командира с непосредственным подчинённым. Такое общение происходит по локальной сети штаба. Каждый военный имеет в штабе собственный компьютер; компьютеры пронумерованы числами от $1$ до $N$, где $N$ — численность марсианской армии. С давних пор повелось, что компьютер подчинённого имеет номер строго больше компьютера командира. Военные, кроме номера компьютера, характеризуются своей надёжностью — действительным числом: владелец компьютера $i$ имеет надёжность $A_i$. Все на Марсе знают, что надёжность генерала равна $1$, а надёжность рядовых (рядовые и только они на Марсе не имеют подчинённых) равна $0$.

Наивно думать, что траффик внутри сети штаба ни во что не обходится военным. За каждый мегабайт траффика между $i$-м компьютером и компьютером командира владельца $i$-го компьютера главный марсианский провайдер требует плату в $C_i$ золотых. Ситуацию осложняет то, что объём траффика между любой парой компьютеров в штабе является государственной тайной, и даже провайдеру он неизвестен. Провайдер поступает следующим образом: раз в месяц он присылает счёт, а военные сами вписывают в него траффик за месяц — неотрицательное число мегабайт. Пусть командир и подчинённый имеют компьютеры с номерами $i$ и $k$ соответственно. По договору с провайдером траффик по счёту между компьютерами $i$ и $k$ не должен быть меньше $A_{i} - A_{k}$. В начале нового месяца представителям провайдера известна иерархия чинов в марсианской армии и цены за мегабайт траффика, однако неизвестны $A_i$ всех чинов, кроме генерала и рядовых, и уж, конечно, неизвестны заранее те суммы в мегабайтах, которые военные впишут в счёт. Хотелось бы знать, какое гарантированное количество золотых может получить провайдер.

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

$2 ≤ N ≤ 100000$ — численность армии. $N-1$ пар целых чисел $K_i$, $C_i$ — номер компьютера командира владельца $i$-го компьютера и стоимость мегабайта траффика между компьютерами $i$ и $K_i$. $1 \leq K_{i} < i \leq N$, $0 \leq C_{i} \leq 1000$.

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

[svv]

Мне кажется, за одну лишь формализацию такой задачи надо брать плату в $C$ золотых.

[b322730]

У меня ошибка -- вместо 2 -- численность армии, надо $2\leq N \leq 100000$