Юбилейный вечер
Ректор Уральского Государственного Университета решил организовать юбилейный вечер к 80-летию основания университета. Университет имеет иерархическую структуру работников, то есть отношения руководителей и подчинённых образуют дерево, в корне которого находится ректор. Сотрудники нумеруются целыми числами в диапазоне от 1 до N. Отдел кадров предоставил информацию о праздничном настроении каждого сотрудника. Для того, чтобы сделать юбилейный вечер приятным для всех его участников, ректор не хочет, чтобы в нём одновременно принимали участие сотрудник и его непосредственный начальник.
Ваша задача составить для ректора список гостей с максимальным праздничным настроением.
Входные данные
Первая строка содержит количество сотрудников университета N ( 1 ≤ N ≤ 6000).
Каждая из последующих N строк содержит праздничное настроение соответствующего сотрудника. Праздничное настроение является целым числом в пределах от –128 до 127. После этого задано дерево отношений сотрудников и их руководителей. Каждая строка описания дерева имеет вид:
L K
что означает, что K-ый работник является непосредственным руководителем L-го работника. Входные данные заканчиваются строкой, содержащей два нуля (эта строка не обрабатывается):
0 0
Выходные данные
Вывод должен содержать максимальное суммарное праздничное настроение гостей.