City Upgrading

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 $a_i$ 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?

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 two integers $n$ $(2≤n≤ 10^5)$ — the number of the vertices in the given tree.

The second line of each case are $n$ integers $a_i(1\le a_i \le 10^5)$,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\cdot 10^5$

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

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

2023“钉耙编程”中国大学生算法设计超级联赛（1）