Ієрархічна структура працівників
Настав час щорічного виїздного засідання у компании 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.
Вихідні дані
Для кожного тесту у окремому рядку вивести максимальний можливий середній індекс веселощів, округлений до трьох десяткових знаків.