Нестабільність дерева
Є дерево з 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 рядків. Кожен рядок містить найменше мождиве значення нестабільності дерева для відповідного тесту.