В Семи Королевствах n городов и n - 1 дорога, каждая дорога соединяет два города, и возможно достичь каждый город из каждого, передвигаясь по дорогам.
Теон и Яра Грейджой начинают путешествовать на лошади по дорогам из первого города. Из-за тумана они не видят, куда лошадь их везет. Когда лошадь входит в город (в том числе в первый), она направляется в один из городов, соединенных с ним. Но это странная лошадь, поэтому она пойдет только в город, в котором до этого не была. Она идет равновероятно в каждый из таких городов и останавливается, если таких городов нет.
Пусть длина каждой дороги 1. Путешествие начинается в городе 1. Чему равно математическое ожидание длины их путешествия? Формально, математическое ожидание — это ожидаемое (то есть среднее) значение. Подробнее можно прочесть по ссылке https://ru.wikipedia.org/wiki/Математическое_ожидание.
Первая строка содержит одно целое число n (1 ≤ n ≤ 100000) — количество городов.
Далее следует n - 1 строк. i-я из них содержит два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — номера городов, соединенных i-й дорогой.
Гарантируется, что возможно достичь каждый город из каждого, передвигаясь по дорогам.
Выведите одно число — математическое ожидание длины путешествия. Путешествие начинается в городе 1.
Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 6.
А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если 
.
4
1 2
1 3
2 4
1.500000000000000
5
1 2
1 3
3 4
2 5
2.000000000000000
В первом примере путешествие может закончиться в городах 3 или 4 с равной вероятностью. Расстояние до городов 3 и 4 равно 1 и 2, соответственно, поэтому матожидание длины равно 1.5.
Во втором примере путешествие может закончиться в городах 4 или 5. Расстояние до обоих городов 2, поэтому матожидание равно 2.
| Codeforces Round 428 (Div. 2) |
|---|
| Закончено |
