Наступило время ежегодного выездного заседания в компании Air Conditioning Machinery (ACM). Все работники восхищены им. Компания имеет иерархическую структуру с одним генеральным директором во главе. Каждый работник докладывает о результатах своей деятельности менеджеру, который находится в иерархической структуре на один уровень выше. С каждым работником e связан индекс веселья F(e), который указывает на уровень комфорта работы с ним.
Алиса занята тем что сосставляет выездные группы. Менеджер любого работника будет в ярости, если одного из его подчиненного пригласят принять участие в выездном заседании, а его нет. Поэтому Алиса должна составить группу так что:
Генеральный директор принадлежит группе (что очевидно)
Для каждого работника, присутствующего в группе, его менеджер также должен присутствовать в группе.
Алиса хочет вычислить максимальный возможный средний индекс веселья группы, которую она может составить. Можете ли Вы ей помочь?
Генеральный директор - это работник, имеющий всегда номер 1. Средний индекс веселья группы равен среднему арифметическому индексов веселья всех членов группы.
Первая строка содержит количество тестов t.
Первая строка каждого теста содержит количество работников N.
Следующая строка содержит N чисел, разделенных пробелом, где i-ое число обозначает индекс веселья F(i) для работника с номером i.
Каждая из следующих N-1 строк содержит два числа a и b которые обозначают что b докладывает о своей работе a. (1 ≤ a, b ≤ N).
Известно, что 1 ≤ t ≤ 20, 1 ≤ N ≤ 50000, 0 ≤ F(i) ≤ 10000.
Для каждого теста в отдельной строке вывести максимальный возможный средний индекс веселья, округленный до трех десятичных знаков.