eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Покраска ребер

Покраска ребер

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Вам дано дерево T из n вершин. Вершины дерева пронумерованы целыми числами от 1 до n. Рассмотрим набор из различных цветов, пронумерованных целыми числами от 1 до n - 1. Каждый цвет имеет стоимость. Вам дана последовательность стоимостей цветов cost[1], cost[2], ..., cost[n−1]. Ваша задача - покрасить каждое ребро в свой цвет таким образом, чтобы любые два инцидентных ребра были покрашены в разные цвета и сумма стоимостей цветов на ребрах была минимальной.

Входные данные

Первая строка содержит количество тестов t (1t16).

Первая строка тествого примера содержит целое число n (1n100). Вторая строка содержит n - 1 целое положительное число cost[1], cost[2], ..., cost[n−1] (1cost[color]1000). Каждая из следующих n - 1 строк содержит два числа u и v - очередное ребро дерева T.

Выходные данные

Для каждого теста выведите в отдельной строке одно целое число - стоимость самой дешевой допустимой реберной покраски дерева.

Пример

Входные данные #1
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
Выходные данные #1
7
31