Друг Хайди Дженни просит ее доставить важное письмо их общему другу. Поскольку Дженни ирландка, Хайди считает, что это может быть шутка. Точнее, она подозревает, что сообщение, которое она попросила доставить, гласит: «Отправьте дурака дальше!», и, читая его, получатель попросит Хайди передать то же сообщение другому другу (общему для получателя и Хайди), и так далее.
Хайди считает, что ее друзья хотят избежать неловких ситуаций, поэтому она не сможет дважды посетить одного и того же человека (включая Дженни). Она также знает, какова стоимость путешествий между любыми двумя друзьями, которые знают друг друга. Она хочет знать: какова максимальная сумма денег, которую она потратит на путешествие, если это действительно шутка?
У Хайди есть n друзей, пронумерованных от 0 до n - 1, и их дружеские связи образуют дерево. Другими словами, каждые двое из ее друзей a и b знают друг друга, возможно, косвенно (то есть существует последовательность друзей, начинающаяся с a и заканчивающаяся b такая, что каждые два последовательных друга в этой последовательности знают друг друга напрямую). Есть ровно n - 1 пара друзей, которые знают друг друга напрямую.
Дженни имеет номер 0.
Примечание
Во втором примере наихудший сценарий выглядит следующим образом: Дженни отправляет Хайди к другу, помеченному номером 2 (Хайди расходует на это 100). Потом друг 2 отправляет Хайди к другу 1 (Хайди тратит на это 3). Затем 1 направляет ее к другу 4 (Хайди расходует на это 2).