Вам дано дерево, состоящее из \(n\) вершин. На каждой вершине записано число; число на вершине \(i\) равно \(a_i\).
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
- выбрать вершину, имеющую не более \(1\) инцидентного ребра, и удалить ее из дерева.
Обратите внимание, что вы можете удалить все вершины.
После выполнения всех операций происходит сжатие дерева. Процесс сжатия выполняется следующим образом. Пока в дереве есть вершина, имеющая ровно \(2\) инцидентных ребра, выполняется следующую операцию:
- удалить эту вершину, а ее соседей соединить ребром.
Можно показать, что если существует несколько способов выбрать вершину для удаления в процессе сжатия, итоговое дерево остается тем же самым.
Ваша задача — вычислить максимально возможную сумму чисел, записанных на вершинах, после применения вышеописанной операции любое количество раз, а затем сжатия дерева.
Выходные данные
Для каждого набора входных данных, выведите одно целое число — максимально возможную сумму чисел, записанных на вершинах, после применения вышеописанной операции любое количество раз, а затем сжатия дерева.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 -2 2 1
1 2
3 2
2 4
2
-2 -5
2 1
7
-2 4 -2 3 3 2 -1
1 2
2 3
3 4
3 5
4 6
4 7
|
3
0
9
|