У Поликарпа есть неориентированный связный граф с N вершинами и N - 1 ребром. У каждой вершины записано целое число vi, где i — номер вершины. Далее Поликарп выполняет следующий алгоритм:
- Равновероятно выбирается произвольная вершина, Поликарп переходит туда.
- Пусть у текущей вершины есть m непосещенных смежных вершин. Тогда с одинаковой вероятностью
Поликарп выбирает одну из этих вершин или алгоритм прекращает работу. - Если Поликарп выбрал вершину, то он переходит в неё, алгоритм переходит к шагу 2.
После того, как алгоритм закончит свою работу, у всех посещенных вершин выписываются числа и складываются. Поликарпу, а заодно и вам, нужно найти математическое ожидание данной суммы.
В первой строке записано число N, 1 ≤ N ≤ 100000. Во второй строке записаны числа vi, i = 1... N, - 1000 ≤ vi ≤ 1000. В следующих N - 1 строках записаны пары чисел ai, bi, 1 ≤ ai, bi ≤ N — ребра графа.
Все числа разделены пробелами между собой в одной строке.
Единственное число — математическое ожидание суммы с точностью не менее 10 - 4.
3
5 4 2
1 2
2 3
6.361111
5
10 20 30 40 50
1 2
1 3
1 4
1 5
50.100000
Пояснение к первому примеру. Путь выбирается вторая вершина. Тогда с вероятностью 
процесс останавливается, с вероятностью происходит переход в первую вершину и, наконец, с вероятностью — в третью. Если выбирается первая, то возможен переход во вторую с вероятностью 
, а оттуда — в третью c такой же вероятностью. Для третьей все происходит аналогично первой.
Если распишем итоговое выражение, получаем:
