Tree Edges Coloring#983
You are given a tree of nodes. The nodes of the tree are numbered from to . Consider a set of different colors numbered from to n-1. Each color has an associated cost. You are given a sequence of color costs: cost_1, cost_2, \ldots, cost_{n-1}.
For each edge, you must choose exactly one color, such that no two incident edges have the same color, and the sum of the chosen color costs is minimized.
The first line contains one integer (1 \leq t \leq 16), the number of test cases.
The first line of each test case contains an integer (1 \leq n \leq 100). The second line contains n-1 positive integers cost_1, cost_2, \ldots, cost_{n-1} (1 \leq cost_{\text{color}} \leq 1000). Each of the next n-1 lines contains two integers and representing an edge of the tree .
For each test case, output a single integer: the cost of the cheapest valid edge coloring.
Example 1