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

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

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

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

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

Repovive

Merge Three Vertices - Repovive Premier Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

6E. Merge Three Vertices

2500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given a tree with $n$ vertices. Each vertex $v$ has an integer value $a_v$ (it may be negative).

In one operation, choose three distinct vertices $v,u,w$ such that $v$ is adjacent to $u$ and $u$ is adjacent to $w$ , so $v-u-w$ is a path of length $2$ and $u$ is the middle vertex.

Then vertices $v$ and $w$ are deleted, and vertex $u$ stays. For every former neighbor $x$ of $v$ with $x \ne u$ , add an edge between $x$ and $u$ . For every former neighbor $y$ of $w$ with $y \ne u$ , add an edge between $y$ and $u$ . The value of $u$ remains $a_u$ . After this operation, the graph is still a tree.

You may perform any number of operations (possibly zero). Your goal is to maximize the sum of values of the remaining vertices.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$-10^9 \le a_v \le 10^9$
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.3em] a_1 \quad a_2 \quad \cdots \quad a_n \\[0.3em] v_1 \quad u_1 \\ v_2 \quad u_2 \\ \vdots \\ v_{n-1} \quad u_{n-1} \end{array} \right\} \times t

Output

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

Samples

Input

Case 1

3
-100 5 -100
1 2
2 3

Case 2

Case 3

5
-1 -1 3 -1 -1
1 2
2 3
3 4
4 5

Explanation

Case 1

Apply an operation on path $1-2-3$ .

Case 2

Don't apply any operations.

Case 3

Apply an operation on path $2-3-4$ to obtain path $1-3-5$ , and then apply an operation on this path.

Output

Case 1

Case 2

Case 3

You are given a tree with $n$ vertices. Each vertex $v$ has an integer value $a_v$ (it may be negative).

In one operation, choose three distinct vertices $v,u,w$ such that $v$ is adjacent to $u$ and $u$ is adjacent to $w$ , so $v-u-w$ is a path of length $2$ and $u$ is the middle vertex.

You may perform any number of operations (possibly zero). Your goal is to maximize the sum of values of the remaining vertices.

Constraints

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

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

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

Apply an operation on path $1-2-3$ .

Apply an operation on path $2-3-4$ to obtain path $1-3-5$ , and then apply an operation on this path.