#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/9/problems/e

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/9/problems/e

Meximus Decimus - Repovive Premier Round 4 | Repovive | Repovive

9E. Meximus Decimus

3000 pts2s256 MB

In the land of Repovive, there are $n$ cities numbered $1$ through $n$ , connected by roads that form a tree. Initially, city $i$ has $a_i$ soldiers.

Meximus Decimus Meridius wants to maximize the country's total military strength. As you can see on his name, he really likes MEX. So he may perform the following operation as many times as he wishes:

Pick two adjacent cities $u$ and $v$ . Let $x$ and $y$ be their current soldier counts, respectively. Then replace both $a_u$ and $a_v$ with $mex(\{x,y\})$ . Let $x$ and $y$ be their current soldier counts ( actually value of $a_u$ and $a_v$ at that moment)
Then replace both $a_u$ and $a_v$ with $\operatorname{mex}(\{x, y\})$ — the smallest non-negative integer that does not appear in the set $\{x, y\}$ .

What is the maximum possible value of $\sum_{i=1}^n a_i$ after any sequence of operations?

Constraints

$1 \le t \le 1000$
$1 \leq n \leq 3 \times 10^5$
$0 \leq a_i \leq 10^9$
the sum of $n$ over all test cases is at most $3 \times 10^5$

Input

$t$

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

$ans \; \} \times t$

Samples

Input

Case 1

2
3 0
1 2

Case 2

6
6 0 1 0 1 1
1 2
2 3
1 4
4 5
1 6

Case 3

6
6 0 0 0 0 1
1 2
2 3
1 4
4 5
1 6

Explanation

Case 1

No operation can increase the sum. Initially $a = [3, 0]$ with sum $3$ . Operating on the two cities gives $\operatorname{mex}(\{3, 0\}) = 1$ , replacing both with $1$ and reducing the sum to $2$ . So the maximum is the initial sum $3$ .

Case 2

Pair each $0$ with a $1$ : $\operatorname{mex}(\{0, 1\}) = 2$ . After two such operations we get $[6, 2, 2, 2, 2, 1]$ , yielding sum $6 + 2 + 2 + 2 + 2 + 1 = 15$ .

Case 3

it's possible to make $[2, 2, 2, 2, 2, 2]$

Output

Case 1

Case 2

Case 3

In the land of Repovive, there are $n$ cities numbered $1$ through $n$ , connected by roads that form a tree. Initially, city $i$ has $a_i$ soldiers.

Pick two adjacent cities $u$ and $v$ . Let $x$ and $y$ be their current soldier counts, respectively. Then replace both $a_u$ and $a_v$ with $mex(\{x,y\})$ . Let $x$ and $y$ be their current soldier counts ( actually value of $a_u$ and $a_v$ at that moment)
Then replace both $a_u$ and $a_v$ with $\operatorname{mex}(\{x, y\})$ — the smallest non-negative integer that does not appear in the set $\{x, y\}$ .

What is the maximum possible value of $\sum_{i=1}^n a_i$ after any sequence of operations?

$1 \le t \le 1000$
$1 \leq n \leq 3 \times 10^5$
$0 \leq a_i \leq 10^9$
the sum of $n$ over all test cases is at most $3 \times 10^5$

$t$

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

$ans \; \} \times t$

Pair each $0$ with a $1$ : $\operatorname{mex}(\{0, 1\}) = 2$ . After two such operations we get $[6, 2, 2, 2, 2, 1]$ , yielding sum $6 + 2 + 2 + 2 + 2 + 1 = 15$ .

it's possible to make $[2, 2, 2, 2, 2, 2]$