Merge Three Vertices - Repovive Premier Round 1 | Repovive

2E. Merge Three Vertices

2500 pts2s256 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.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

2E. Merge Three Vertices

Input

Output

Samples

2E. Merge Three Vertices

Constraints

Input

Output

Samples

Constraints