Halving - Repovive Standard Round 8 | Repovive

26E. Halving

2500 pts2s256 MB

You are given a tree with $n$ vertices. A positive integer $a_v$ is written on vertex $v$ .

In one move, choose either a connected component of the subgraph induced by the vertices whose current numbers are even, or a connected component of the subgraph induced by the vertices whose current numbers are odd. Replace the number on every vertex $v$ of the chosen component with $\lfloor a_v/2\rfloor$ .

You must choose the entire component; choosing only part of it is not allowed.

Immediately after the move, delete every vertex whose number becomes zero, together with all edges incident to it. The remaining graph may be a forest, and subsequent moves are performed on this graph.

Find the minimum number of moves needed to delete all vertices.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_v \le 1000$
$1 \le u_i,v_i \le n$
The given edges form a tree.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \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

Each pair $u_i,v_i$ describes an edge of the tree. For $n=1$ , there are no edge lines.

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, output the minimum number of moves needed to delete all vertices.

Samples

Input

Case 1

1
1000

Case 2

Explanation

Case 1

The only vertex changes as follows: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, 0. This requires ten moves.

Case 2

Halve vertex 1, then vertex 3. All three numbers are now 1, so the entire tree can be deleted in one move. Two moves cannot suffice: both endpoints need to be halved twice, but they cannot be selected together in the first move.

Output

Case 1

Case 2

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Halve the middle vertex. All numbers become 1, and the next move deletes the entire tree. One move is insufficient because the middle vertex needs two halvings.

Case 2

First halve the entire tree, obtaining 1, 2, 1. Then halve the middle vertex and finally delete the entire tree. At least three moves are necessary because the middle number, initially 5, needs three halvings.

Case 3

Halve each of the three leaves separately, then delete the entire tree. Each leaf needs an even move before it becomes odd. These three even moves affect separate components, and at least one further move is needed.

Output

Case 1

Case 2

Case 3

You are given a tree with $n$ vertices. A positive integer $a_v$ is written on vertex $v$ .

You must choose the entire component; choosing only part of it is not allowed.

Find the minimum number of moves needed to delete all vertices.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_v \le 1000$
$1 \le u_i,v_i \le n$
The given edges form a tree.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \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

Each pair $u_i,v_i$ describes an edge of the tree. For $n=1$ , there are no edge lines.

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

For each test case, output the minimum number of moves needed to delete all vertices.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

26E. Halving

Constraints

Input

Output

Samples

26E. Halving

Constraints

Input

Output

Samples