Самый ценный участок пути


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Самый ценный участок пути

Сеть из n узлов — дерево, в каждом узле записано число cᵢ (может быть отрицательным). Выберите простой путь (хотя бы из одного узла) с наибольшей суммой чисел в его узлах.

Ввод. В первой строке n (1 ≤ n ≤ 10⁵). Во второй — n чисел cᵢ (|cᵢ| ≤ 10⁴). Далее n-1 строка с парами a b.

Вывод. Одно число.

Пример 1

Ввод

5
-3 4 -1 5 2
1 2
2 3
2 4
4 5

Вывод

11

Комментарии

Еще нет ни одного комментария.