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

Нестабильность дерева

Нестабильность дерева

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

Имеется дерево с N вершинами. С каждой вершиной u дерева связана его стоимость c_u. Определим нестабильность дерева с корнем следующим образом:

Через L_i обозначен уровень вершины i по отношению к корню дерева. Корень всегда имеет уровень 0. Вам необходимо выбрать в дереве корень таким образом, чтобы минимизировать значение нестабильности дерева.

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

Первая строка содержит количество тестов T. Первая строка каждого теста содержит количество вершин в дереве N. Следующая строка содержит N целых чисел, разделенных пробелом, где i-ое число является стоимостью i-ой вершины дерева. Каждая из следующих N-1 строк содержит два целых числа a и b (1a, bN), описывающие ребро между вершинами a и b.

Известно, что 1T 20, 1N20000, 1c_i1000.

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

Состоит из T строк. Каждая строка содержит наименьшее возможное значение нестабильности дерева для соответствующего теста.

Пример

Входные данные #1
1
3
10 15 20
1 2
1 3
Выходные данные #1
720
Автор Аджай Сомани
Источник Севастополь - 2010