题目描述
View Russian Translation
You are given a tree T of n nodes. The nodes in the tree are numbered 1 through n. Let's consider some set of different colors numbered 1 through n - 1. Each color costs differently. You are given a sequence cost_1, cost_2, ..., cost_{n-1} of the color costs.
For each edge, you should choose exactly one color in such a way that no two incident edges have the same color and the sum of the chosen color costs is as minimal as possible.
More formally, let's assign some unique integer from 1 to n - 1 to each of the edges of T. A sequence c_1, c_2, ..., c_{n-1} (1 ≤ c_k ≤ n - 1) is called an edge coloring of the tree; c_k is called the color of the k'th edge. An edge coloring is called valid, if there is no such a pair of edges, that share a common node and have the same color.
The cost of an edge coloring is the sum of the color costs for all the edges of the tree. Your task is to find the cost of the cheapest valid edge coloring.
Input format
The first line contains one integer t denoting the number of test cases in the input.
The first line of each test case description contains an integer n.
The second line contains n - 1 positive integers denoting cost_1, cost_2, ..., cost_{n-1}.
Each of the next n - 1 lines contains two integers u and v denoting an edge of the tree.
Output format
For each test case, output a single integer: the cost of the cheapest valid edge coloring.
Constraints
1 ≤ t ≤ 16
1 ≤ n ≤ 100
1 ≤ cost_{color} ≤ 1000
SAMPLE INPUT
2
5
1 2 3 4
1 2
2 3
2 4
4 5
6
16 4 1 8 2
1 3
3 5
6 3
3 2
4 3
SAMPLE OUTPUT
7
31
Explanation
Let's number the edges of the sample trees as they go in the input.
The first test case of the sample input: one of the optimal edge colorings is (1, 2, 3, 1).
The second test case of the sample input: one of the optimal edge colorings is (1, 2, 3, 4, 5).
输入格式
见题面
输出格式
见题面