Легенда

В город Новоомулевск приехал новый ведущий инженер-энергетик Виталий Солнцев, и он решил проверить, насколько эффективно работает местная электросеть. Первым делом, Виталий узнал, что у города есть главная подстанция, в которую перетекает мощность со всех объектов сети. Объектами могут быть как генераторы (электростанции), так и потребители (дома). В связи со сложностью расположения объектов, в мощности, перетекающей по проводам, происходят потери.

Вам дана сеть с виде дерева. Каждый узел дерева, кроме нулевого (это главная подстанция) является потребителем или генератором. На перетекаемую мощность по линии накладываются потери в 20% — генерация уменьшается, потребление возрастает. Помогите Виталию рассчитать общий дефицит или избыток мощности, пришедшей на главную подстанцию.

Формат входных данных: первая строка — единственное число N, количество узлов (считая главную подстанцию). В следующей строке приводится N чисел — собственные мощности каждого узла (0-й узел всегда имеет нулевую мощность, потребление выражается отрицательным числом, генерация – положительным). Далее в N-1 строках приводятся соединяемые узлы в виде двух номеров через пробел.

4
0 -10 20 3
1 0
2 1
3 1

Формат выходных данных: вещественное число — мощность, приходящая на 0-й узел. Ответ принимается, если значение отличается от эталонного не больше, чем на 10–6.

Для решения этой задачи у вас есть 20 попыток.

Time Limit: 5 секунд

Memory Limit: 256 MB

Видео-разбор


Last modified: Saturday, 30 December 2023, 8:46 PM