Сильная группа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Место, где живут тёмные эльфы, представляет собой пещеру, в которой есть $$$n$$$ помещений, пронумерованных от $$$1$$$ до $$$n$$$, соединенных $$$n - 1$$$ узким проходом. Причем, из любого помещения по проходам достижимо любое другое. В каждом помещении живёт ровно один тёмный эльф, а в проходах не живёт никто. В $$$i$$$-м помещении живёт эльф номер $$$i$$$. У каждого эльфа есть значение $$$w_i$$$ — его сила в бою.

Малефисента собирается в замок королевы Ингрит. Совет тёмных эльфов решил отправить вместе с ней группу эльфов, такую что в ней будет хотя бы два эльфа, и помещения, в которых живут эльфы, входящие в группу, образуют связную область. Иными словами, для любых двух эльфов $$$a$$$ и $$$b$$$, входящих в группу, все эльфы, живущие в помещениях на простом пути между помещениями $$$a$$$ и $$$b$$$, также должны входить в группу. Разумеется, Малефисенту должен сопровождать наиболее сильный отряд, поэтому совет хочет выбрать такую группу, чтобы среднее арифметическое силы участников группы было максимально. Помогите совету найти это значение.

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

В первой строке дано целое число $$$n$$$ — количество помещений в пещере ($$$2 \le n \le 200\,000$$$). В следующей строке даны $$$n$$$ целых чисел $$$w_i$$$ — сила $$$i$$$-го эльфа в бою ($$$0 \le w_i \le 10^9$$$). В следующих $$$n - 1$$$ строках даны по два целых числа $$$a_i$$$ и $$$b_i$$$ — номера помещений, которые соединены проходом ($$$1 \le a_i, b_i \le n$$$). Гарантируется, что из любого помещения можно добраться до любого другого по проходам.

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

Выведите единственное число — максимальное среднее арифметическое силы участников группы. Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает $$$10^{-6}$$$.

Примеры

Входные данные
3
1 2 3
1 2
2 3
Выходные данные
2.500000000000000
Входные данные
3
7 1 7
1 2
2 3
Выходные данные
5.000000000000000
Входные данные
4
7 1 7 7
1 2
2 3
2 4
Выходные данные
5.500000000000000