F. Плюс-минус дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево $$$T$$$ из $$$n$$$ вершин с корнем$$$^{\text{∗}}$$$ в вершине $$$1$$$. Каждой вершине $$$v$$$ присвоен исходный вес $$$ a_v \in \{ -1, 0, +1 \} $$$.

Каждой вершине с весом $$$0$$$ нужно присвоить новый вес, равный либо $$$-1$$$, либо $$$+1$$$. Обозначим через $$$x_v$$$ итоговый вес вершины $$$v$$$.

Для вершины $$$v$$$ пусть $$$T_v$$$ — множество вершин в поддереве$$$^{\text{†}}$$$ вершины $$$v$$$. Стоимость вершины $$$v$$$ определяется следующим образом: $$$$$$ S_v = \left| \sum_{u \in T_v}{x_u} \right|.$$$$$$

Суммарная стоимость дерева определяется как сумма стоимостей всех вершин. Найдите наименьшую возможную суммарную стоимость дерева после присвоения весов всем вершинам, исходный вес которых нулевой.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем.

$$$^{\text{†}}$$$Поддеревом вершины $$$v$$$ называется подграф, состоящий из вершины $$$v$$$, всех ее потомков, и всех ребер между ними. Потомком вершины $$$v$$$ называется любая вершина $$$u$$$, для которой $$$v$$$ является предком. Никакая вершина не является своим потомком. Предком вершины $$$v$$$ называется любая вершина на пути от $$$v$$$ до корня, включая корень, но не включая $$$v$$$. У корня нет предков.

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

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

В первой строке каждого набора входных данных содержится $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le 1$$$).

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимальную суммарную стоимость дерева.

Пример
Входные данные
2
5
0 1 -1 0 1
1 2
1 3
2 4
2 5
8
1 -1 1 -1 1 -1 1 -1
1 2
2 3
2 4
3 5
4 6
6 7
2 8
Выходные данные
5
7
Примечание

Оптимальные присвоения весов в первом наборе входных данных имеют вид $$$[+1, +1, -1, -1, +1]$$$ и $$$[-1, +1, -1, -1, +1]$$$. Их стоимость равна $$$5$$$.

Другое присвоение $$$[+1, +1, -1, +1, +1]$$$ имеет стоимость $$$9$$$, а $$$[-1, +1, -1, +1, +1]$$$ имеет стоимость $$$7$$$.

Дерево из первого набора входных данныхДерево из второго набора входных данных