F. Plus Minus Tree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree $$$T$$$ with $$$n$$$ vertices, rooted$$$^{\text{∗}}$$$ at vertex $$$1$$$. Each vertex $$$v$$$ is assigned an initial weight $$$ a_v \in \{ -1, 0, +1 \} $$$.

For each vertex with weight $$$0$$$, you have to assign a new weight, either $$$-1$$$ or $$$+1$$$. Let $$$x_v$$$ be the final weight of vertex $$$v$$$.

For vertex $$$v$$$, let $$$T_v$$$ be the set of nodes in the subtree$$$^{\text{†}}$$$ of vertex $$$v$$$. The cost of vertex $$$v$$$ is defined as $$$$$$ S_v = \left| \sum_{u \in T_v}{x_u} \right|.$$$$$$

The total cost of the tree is defined as the sum of costs over all vertices. Find the minimum possible total cost of the tree after assigning the weights of all vertices with zero initial weight.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

$$$^{\text{†}}$$$A subtree of vertex $$$v$$$ is the subgraph consisting of $$$v$$$, all its descendants, and all the edges between them. A descendant of vertex $$$v$$$ is any vertex $$$u$$$ for which $$$v$$$ is an ancestor. No vertex is its own descendant. An ancestor of vertex $$$v$$$ is any vertex on the simple path from $$$v$$$ to the root, including the root, but not including $$$v$$$. The root has no ancestors.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), denoting the number of vertices in the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le 1$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting the nodes connected with an edge of the tree. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the minimum total cost of the tree.

Example
Input
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
Output
5
7
Note

The best assignments in the first test case are $$$[+1, +1, -1, -1, +1]$$$ and $$$[-1, +1, -1, -1, +1]$$$. They have a cost of $$$5$$$.

Another assignment, $$$[+1, +1, -1, +1, +1]$$$ has a cost of $$$9$$$, and $$$[-1, +1, -1, +1, +1]$$$ has a cost of $$$7$$$.

The tree of the first testcaseThe tree of the second testcase