28736번 - Сильная группа 스페셜 저지다국어

문제

Место, где живут тёмные эльфы, представляет собой пещеру, в которой есть $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}$.

제한

힌트