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