Codeforces Round 958 (Div. 2) |
---|
Закончено |
Вы, убийца монстров, хотите убить группу монстров. Монстры находятся в дереве с $$$n$$$ вершинами. В вершине с номером $$$i$$$ ($$$1\le i\le n$$$) находится монстр с $$$a_i$$$ очками атаки. Вы хотите сражаться с монстрами в течение $$$10^{100}$$$ раундов.
В каждом раунде происходит следующее по порядку:
Также есть следующее ограничение: за один раунд вы не можете убить двух монстров, находящихся в соединенных ребром вершинах.
Если вы оптимально выбираете, каких монстров атаковать на каждом шагу, на какую минимальную величину может уменьшиться ваше здоровье за все раунды?
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество тестов $$$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$$$.
Для каждого набора входных данных выведите одно целое число — минимально возможное уменьшение здоровья.
311000000000000547 15 32 29 231 21 32 42 578 10 2 3 5 7 41 21 43 25 36 27 5
1000000000000 193 57
В первом наборе оптимальная последовательность операций следующая:
Общее уменьшение здоровья составляет $$$10^{12}$$$.
Во втором наборе оптимальная последовательность операций следующая:
Общее уменьшение здоровья составляет $$$193$$$.
В третьем наборе оптимальная последовательность операций следующая:
Общее уменьшение здоровья составляет $$$57$$$.
Название |
---|