Вам дано дерево, состоящее из $$$n$$$ вершин. На каждой вершине записано число; число на вершине $$$i$$$ равно $$$a_i$$$.
Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
Обратите внимание, что вы можете удалить все вершины.
После выполнения всех операций происходит сжатие дерева. Процесс сжатия выполняется следующим образом. Пока в дереве есть вершина, имеющая ровно $$$2$$$ инцидентных ребра, выполняется следующую операцию:
Можно показать, что если существует несколько способов выбрать вершину для удаления в процессе сжатия, итоговое дерево остается тем же самым.
Ваша задача — вычислить максимально возможную сумму чисел, записанных на вершинах, после применения вышеописанной операции любое количество раз, а затем сжатия дерева.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — количество вершин.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
Каждая из следующих $$$n - 1$$$ строк описывает ребра дерева. Ребро $$$i$$$ описывается двумя целыми числами $$$v_i$$$ и $$$u_i$$$, номерами вершин, которые оно соединяет ($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$). Данные ребра образуют дерево.
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных, выведите одно целое число — максимально возможную сумму чисел, записанных на вершинах, после применения вышеописанной операции любое количество раз, а затем сжатия дерева.
341 -2 2 11 23 22 42-2 -52 17-2 4 -2 3 3 2 -11 22 33 43 54 64 7
3 0 9
Название |
---|