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