ЦПСП
(Время: 2 сек. Память: 32 Мб Сложность: 47%)
Министерство образования великой страны N планирует открыть Центр Подготовки Спортивных Программистов в одном из своих городов. Города страны пронумерованы целыми числами от 1 до n и соединены друг с другом n-1 трассой, между любыми двумя городами существует путь по трассам. На каждой трассе разрешено движение в обе стороны.
В каждом городе страны N живёт определённое количество школьников, интересующихся олимпиадами по программированию, все они являются потенциальными учащимися Центра. Ожидается, что в Центр будут поступать не только местные, но и иногородние школьники (для этого им придётся совершить переезд из родного города). Любимая система счисления у программистов — двоичная,
поэтому все школьники умеют совершать переезды, маршрут которых содержит ровно две трассы.
Некоторые города в стране являются тупиковыми — те, которые соединены трассой только с одним городом. Министерство образования запретило строить Центр в тех и только в тех городах, которые соединены трассой хотя бы с одним тупиковым городом, ведь школьники из тупикового города не смогут совершить переезд для поступления, а близость тупиковых детей будет негативно
влиять на работу Центра.
Узнайте, какое максимальное количество иногородних школьников сможет привлечь новый Центр, ведь именно это более всего интересует Министерство образования страны N.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число n (1 ≤ n ≤ 105) — количество городов в стране. В каждой из следующих n−1 строк записаны по два целых числа xi и yi (1 ≤ xi, yi ≤ n; xi ≠ yi), означающие, что города с этими номерами соединены трассой. В последней строке через пробел записано n целых чисел ai — количество школьников из i-го города, интересующихся олимпиадами по программированию (1 ≤ ai ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число, равное искомому максимальному значению.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 2
2 3
1 1 100 | 100 |
| 2 | 5
1 2
2 3
3 4
4 5
1 1 1 1 1 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
