Полезное тепловыделение (НТО 23/24 :: ИЭС)
Легенда
В город Новоомулевск приехал новый ведущий инженер-энергетик Виталий Солнцев, и он решил проверить, насколько эффективно работает местная электросеть. Первым делом, Виталий узнал, что у города есть главная подстанция, в которую перетекает мощность со всех объектов сети. Объектами могут быть как генераторы (электростанции), так и потребители (дома). В связи со сложностью расположения объектов, в мощности, перетекающей по проводам, происходят потери.
Вам дана сеть с виде дерева. Каждый узел дерева, кроме нулевого (это главная подстанция) является потребителем или генератором. На перетекаемую мощность по линии накладываются потери в 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