该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

The city where crazyzhk resides is structured as a tree. On a certain day, the city’s network needs to be upgraded. To achieve this goal, routers need to be deployed. Each router covers the node it is placed on and its neighboring nodes. There is a cost ai associated with placing a router at each node. The question is: How can the routers be deployed at minimum cost to ensure that every node is covered?

Input

The input consists of multiple test cases. The first line contains a single integer t(1 ≤ t ≤ 1000) — the number of test cases. Description of the test cases follows. The first line of each test case contains a integer n ($2 ≤ n ≤ 10^5$ ) — the number of the vertices in the given tree. The second line of each case are n integers ai(1 ≤ ai ≤ 105 ),denoting the cost of setting up a router at each node. Each of the next n − 1 lines contains two integers u and v ($1 ≤ u, v ≤ n, u \neq v$) meaning that there is an edge between vertices u and v in the tree. The data guarantees that the sum of n will not exceed $2 · 10^5$

Output

For each test case print a single integer ——the minimum cost to ensure that every node is covered

Samples

2 
7 
13 20 1 20 6 9 8 
1 2 
1 3 
2 4 
2 5 
3 6 
5 7 
4 
1 17 13 4 
1 2 
1 3 
3 4

27 
5

Limitation

6s, 128mb for each test case.