Нестабильность дерева
Нестабильность дерева
Имеется дерево с N вершинами. С каждой вершиной u дерева связана его стоимость c_u. Определим нестабильность дерева с корнем следующим образом:
Через L_i обозначен уровень вершины i по отношению к корню дерева. Корень всегда имеет уровень 0. Вам необходимо выбрать в дереве корень таким образом, чтобы минимизировать значение нестабильности дерева.
Входные данные
Первая строка содержит количество тестов T. Первая строка каждого теста содержит количество вершин в дереве N. Следующая строка содержит N целых чисел, разделенных пробелом, где i-ое число является стоимостью i-ой вершины дерева. Каждая из следующих N-1 строк содержит два целых числа a и b (1 ≤ a, b ≤ N), описывающие ребро между вершинами a и b.
Известно, что 1 ≤ T ≤ 20, 1 ≤ N ≤ 20000, 1 ≤ c_i ≤ 1000.
Выходные данные
Состоит из T строк. Каждая строка содержит наименьшее возможное значение нестабильности дерева для соответствующего теста.
Пример
1 3 10 15 20 1 2 1 3
720