E. Color the Tree
time limit per test
3 seconds
memory limit per test
1024 MB
input
standard input
output
standard output

There is a rooted tree of $$$n$$$ vertices. The vertices are numbered from $$$1$$$ to $$$n$$$ (both inclusive) and the tree is rooted at $$$1$$$. All of the $$$n$$$ vertices are white at the beginning and you need to color all the vertices black.

To help you achieve the goal we will provide you with $$$n$$$ types of operations, numbered from $$$0$$$ to $$$(n - 1)$$$ (both inclusive). Operation $$$i$$$ ($$$0 \le i \le n - 1$$$) requires you to first select a vertex $$$u$$$, then color all the vertices $$$v$$$ satisfying the following conditions black:

  • Vertex $$$v$$$ is in the subtree rooted at $$$u$$$, which means $$$u = v$$$ or $$$u$$$ is an ancestor of $$$v$$$.
  • The distance between vertices $$$u$$$ and $$$v$$$ is exactly $$$i$$$. Here the distance between $$$u$$$ and $$$v$$$ is the minimum number of edges we need to go through to reach $$$v$$$ from $$$u$$$.

The cost of performing operation $$$i$$$ once is given as $$$a_i$$$. A vertex can be colored more than once and all operations can be performed any number of times. Calculate the minimum total cost to color all the vertices black.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) indicating the size of the tree.

The second line contains $$$n$$$ integers $$$a_0, a_1, \cdots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$) where $$$a_i$$$ indicates the cost of performing operation $$$i$$$ once.

For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) indicating an edge connecting vertices $$$u_i$$$ and $$$v_i$$$.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$3 \times 10^5$$$.

Output

For each test case output one line containing one integer indicating the minimum total cost to color the tree black.

Example
Input
3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4
Output
35
17
1218
Note

The first sample test case is illustrated below. The answer is $$$15 + 10 + 10 = 35$$$.

The second sample test case is illustrated below. The answer is $$$5 + 10 + 1 + 1 = 17$$$.