시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB32266.667%

문제

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

예제 입력 1

3
1 2 3
1 2
2 3

예제 출력 1

2.500000000000000

예제 입력 2

3
7 1 7
1 2
2 3

예제 출력 2

5.000000000000000

예제 입력 3

4
7 1 7 7
1 2
2 3
2 4

예제 출력 3

5.500000000000000