Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

ЦПСП

(Время: 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.TXTOUTPUT.TXT
13
1 2
2 3
1 1 100
100
25
1 2
2 3
3 4
4 5
1 1 1 1 1
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Переполох у турникетов
 B. Поездка в кино
 C. Баобаб
 D. Очистка террасы
 E. Битва школ
 F. Этажи
 G. Космическое сновидение
 H. Неумолкающий Янпул
 I. ЦПСП
 J. Стреляй!
 K. Отряд Стёпы
 L. Swap optimization

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru