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

Чемпионат УрГУ 2000

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

C. Юбилейная вечеринка

Ограничение времени: 0.5 секунды
Ограничение памяти: 8 МБ
Ректор Уральского государственного университета собирается устроить вечеринку по случаю 80-летия университета. Университет имеет иерархическую структуру сотрудников в виде дерева с корнем в ректоре. Чтобы сделать вечеринку веселой для всех присутствующих, ректор не хочет, чтобы кто-то из ее участников мог столкнуться там со своим непосредственным руководителем (это означает, что сотрудник и его непосредственный руководитель не должны быть одновременно приглашены на вечеринку).
Отдел кадров вычислил уровень праздничного настроения каждого сотрудника университета. Ваша задача – составить список гостей с максимальным суммарным уровнем праздничного настроения, выполнив при этом условие ректора.

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

В первой строке записано целое число N – количество сотрудников университета (1 ≤ N ≤ 6000). Сотрудники пронумерованы целыми числами в диапазоне от 1 до N. Каждая из последующих N строк содержит рейтинг праздничного настроения соответствующего сотрудника – целое число в диапазоне от −128 до 127. Затем идет описание дерева структуры сотрудников. Каждая строка описания дерева имеет следующую форму
<L> <K>
это означает, что K-й сотрудник является непосредственным руководителем L-го сотрудника. Ввод заканчивается строкой
0 0

Результат

Выведите максимальный суммарный уровень праздничного настроения гостей.

Пример

исходные данныерезультат
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
5
Автор задачи: Марат Бакиров
Источник задачи: Пятый командный чемпионат УрГУ по программированию (Октябрь 2000 г.)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1039. Юбилейная вечеринка