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