E. Сжатие дерева
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево, состоящее из $$$n$$$ вершин. На каждой вершине записано число; число на вершине $$$i$$$ равно $$$a_i$$$.

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • выбрать вершину, имеющую не более $$$1$$$ инцидентного ребра, и удалить ее из дерева.

Обратите внимание, что вы можете удалить все вершины.

После выполнения всех операций происходит сжатие дерева. Процесс сжатия выполняется следующим образом. Пока в дереве есть вершина, имеющая ровно $$$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$$$.

Выходные данные

Для каждого набора входных данных, выведите одно целое число — максимально возможную сумму чисел, записанных на вершинах, после применения вышеописанной операции любое количество раз, а затем сжатия дерева.

Пример
Входные данные
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