Ювілейний вечір#3526
Ректор Центрально-Європейського Університету вирішив організувати ювілейний вечір до -річчя заснування університету. Університет має ієрархічну структуру працівників, тобто відношення керівників та підлеглих утворюють дерево, у корені якого знаходиться ректор. Співробітників пронумеровано цілими числами у діапазоні від до . Відділ кадрів надав інформацію про святковий настрій кожного співробітника. Для того, щоб зробити ювілейний вечір приємним для усіх його участників, ректор не хоче, щоб у ньому одночасно брали участь співробітник та його безпосередній начальник.
Ваша задача скласти для ректора список гостей з максимальним святковим настроєм.
Перший рядок містить кількість співробітників університету (1 \le N \le 6000). Кожен з наступних рядків містить святковий настрій відповідного працівника. Святковий настрій є цілим числом у межах від до . Після цього задано дерево відношень працівників та їх керівників. Кожен рядок опису дерева має вигляд:
що означає, що -ий працівник є безпосереднім керівником -го працівника. Вхідні дані завершуються рядком, який містить два нулі (цей рядок не опрацьовується):
Вихід повинен містити максимальний сумарний святковий настрій гостей.
Приклад 1