Покраска ребер
Покраска ребер
Вам дано дерево T из n вершин. Вершины дерева пронумерованы целыми числами от 1 до n. Рассмотрим набор из различных цветов, пронумерованных целыми числами от 1 до n - 1. Каждый цвет имеет стоимость. Вам дана последовательность стоимостей цветов cost[1]
, cost[2]
, ..., cost[n−1]
. Ваша задача - покрасить каждое ребро в свой цвет таким образом, чтобы любые два инцидентных ребра были покрашены в разные цвета и сумма стоимостей цветов на ребрах была минимальной.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 16).
Первая строка тествого примера содержит целое число n (1 ≤ n ≤ 100). Вторая строка содержит n - 1 целое положительное число cost[1]
, cost[2]
, ..., cost[n−1]
(1 ≤ cost[color]
≤ 1000). Каждая из следующих n - 1 строк содержит два числа u и v - очередное ребро дерева T.
Выходные данные
Для каждого теста выведите в отдельной строке одно целое число - стоимость самой дешевой допустимой реберной покраски дерева.
Пример
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
7 31