D. Универсальный убийца монстров
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы, убийца монстров, хотите убить группу монстров. Монстры находятся в дереве с $$$n$$$ вершинами. В вершине с номером $$$i$$$ ($$$1\le i\le n$$$) находится монстр с $$$a_i$$$ очками атаки. Вы хотите сражаться с монстрами в течение $$$10^{100}$$$ раундов.

В каждом раунде происходит следующее по порядку:

  1. Все живые монстры атакуют вас. Ваше здоровье уменьшается на сумму очков атаки всех живых монстров.
  2. Вы выбираете некоторых (возможно, всех или ни одного) монстров и убиваете их. После убийства монстр больше не сможет совершать атаки в будущем.

Также есть следующее ограничение: за один раунд вы не можете убить двух монстров, находящихся в соединенных ребром вершинах.

Если вы оптимально выбираете, каких монстров атаковать на каждом шагу, на какую минимальную величину может уменьшиться ваше здоровье за все раунды?

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество тестов $$$t$$$ ($$$1 \le t \le 10^4$$$). Затем следует описание наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 10^{12}$$$).

Следующие $$$n-1$$$ строк каждого набора содержат по два целых числа $$$x,y$$$ ($$$1\le x,y\le n$$$), обозначающих ребро в дереве, соединяющее вершину $$$x$$$ и $$$y$$$.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$3\cdot 10^5$$$.

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

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

Пример
Входные данные
3
1
1000000000000
5
47 15 32 29 23
1 2
1 3
2 4
2 5
7
8 10 2 3 5 7 4
1 2
1 4
3 2
5 3
6 2
7 5
Выходные данные
1000000000000
193
57
Примечание

В первом наборе оптимальная последовательность операций следующая:

  • В первом раунде: сначала получите атаку от монстра в вершине $$$1$$$, поэтому ваше здоровье уменьшается на $$$10^{12}$$$. Затем убейте монстра в вершине $$$1$$$.
  • Во втором раунде до $$$10^{100}$$$-го раунда: все монстры были убиты, поэтому ничего не происходит.

Общее уменьшение здоровья составляет $$$10^{12}$$$.

Во втором наборе оптимальная последовательность операций следующая:

  • В первом раунде: сначала получите атаку от монстров в вершинах $$$1,2,3,4,5$$$, поэтому ваше здоровье уменьшается на $$$47+15+32+29+23=146$$$. Затем убейте монстров в вершинах $$$1,4,5$$$.
  • Во втором раунде: сначала получите атаку от монстров в вершинах $$$2,3$$$, поэтому ваше здоровье уменьшается на $$$15+32=47$$$. Затем убейте монстров в вершинах $$$2,3$$$.
  • В третьем раунде до $$$10^{100}$$$-го раунда: все монстры были убиты, поэтому ничего не происходит.

Общее уменьшение здоровья составляет $$$193$$$.

В третьем наборе оптимальная последовательность операций следующая:

  • В первом раунде: сначала получите атаку от монстров в вершинах $$$1,2,3,4,5,6,7$$$, поэтому ваше здоровье уменьшается на $$$8+10+2+3+5+7+4=39$$$. Затем убейте монстров в вершинах $$$1,3,6,7$$$.
  • Во втором раунде: сначала получите атаку от монстров на вершинах $$$2,4,5$$$, поэтому ваше здоровье уменьшается на $$$10+3+5=18$$$. Затем убейте монстров на вершинах $$$2,4,5$$$.
  • В третьем раунде до $$$10^{100}$$$-го раунда: все монстры были убиты, поэтому ничего не происходит.

Общее уменьшение здоровья составляет $$$57$$$.