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

$ curl repovive.com/contests/6/problems/F

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

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

$ curl repovive.com/contests/6/problems/F

Repovive

Consecutive Subtree - Repovive Premier Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

6F. Consecutive Subtree

3000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given a tree with $n$ vertices labeled $1,2,\dots,n$ . Each vertex $v$ has a (possibly negative) cost $a_v$ .

The tree is rooted at vertex $1$ .

Your goal is to delete all vertices using the following operation with minimum total cost.

In one operation, choose a vertex $v$ . Let $S$ be the set of vertices in the subtree of $v$ . If the labels in $S$ form a set of consecutive integers, you may delete all vertices in $S$ and pay cost $a_v$ .

Find the minimum possible total cost.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$-10^6 \le a_v \le 10^6$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t \\[0.5em] \left. \begin{array}{l} n \\[0.25em] a_1 \quad a_2 \quad \dots \quad a_n \\[0.25em] u_1 \quad v_1 \\[-0.15em] u_2 \quad v_2 \\[-0.15em] \vdots \\[-0.15em] u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Samples

Input

4
1
5
4
3 -5 4 1
1 2
2 3
2 4
5
2 7 -3 1 -4
1 2
2 3
3 4
4 5
6
10 -8 5 -2 7 -6
1 3
3 2
3 4
4 5
4 6

Explanation

Case 1

Choose vertex $1$ .
Its subtree is $\{1\}$ , so we delete it and pay $5$ .

Case 2

Choose vertex $2$ first.
Its subtree is $\{2,3,4\}$ , so we delete $2,3,4$ and pay $-5$ .
Now only $\{1\}$ remains, choose $1$ and pay $3$ .

Case 3

Choose vertex $5$ first.
Its subtree is $\{5\}$ , so we delete $5$ and pay $-4$ .
Now the subtree of $3$ is $\{3,4\}$ , so choose $3$ , delete $3,4$ , and pay $-3$ .
Now the subtree of $1$ is $\{1,2\}$ , so choose $1$ , delete $1,2$ , and pay $2$ .

Case 4

Choose vertex $2$ first.
Its subtree is $\{2\}$ , so we delete $2$ and pay $-8$ .
Choose vertex $6$ . Its subtree is $\{6\}$ , so we delete $6$ and pay $-6$ .
Now the subtree of $4$ is $\{4,5\}$ , so choose $4$ , delete $4,5$ , and pay $-2$ .
Then choose $3$ (subtree $\{3\}$ ) and pay $5$ .
Finally choose $1$ (subtree $\{1\}$ ) and pay $10$ .