Лабиринт представляет из себя дерево (неориентированный граф, в котором между любой парой вершин существует ровно один путь). В лабиринте с определенной вероятностью выбираются вершины входа и выхода. Выход из лабиринта ищется при помощи обхода в глубину, в случае нескольких возможных ходов, ход выбирается равновероятно. Рассмотрим псевдокод:
DFS(x)
if x == вершина выхода then
завершить обход дерева
flag[x] <- TRUE
перемешать порядок вершин в V(x) // здесь каждая перестановка V(x) равновероятна
for i <- 1 to length[V] do
if flag[V[i]] = FALSE then
count++;
DFS(V[i]);
count++;
V(x) — список вершин смежных с x. Массив flag изначально заполнен FALSE. Изначально DFS запускается с параметром вершины входа. По завершению обхода в переменной count будет находится количество ходов.
Требуется посчитать математическое ожидание количества ходов для нахождения выхода из лабиринта.
Выходные данные
Выведите матожидание количества ходов. Абсолютная или относительная погрешность не должна превосходить 10 - 9.
Примечание
В первом примере вершина входа всегда 1 и вершина выхода всегда 2.
Во втором примере вершина входа всегда 1, вершина выхода с вероятностью 2/5 будет 2 или с вероятность 3/5 будет 3. Матожидания для вершин выхода 2 и 3 будут равны (симметричные случаи). На первом ходе с вероятностью 0.5 можно пойти в вершину выхода или с вероятностью 0.5 не в вершину выхода. В первом случаи количество ходов равно 1, во втором оно будет равно 3. Итоговое матожидание считается как 2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
0 1
1 0
|
1.00000000000000000000
|
|
2
|
3
1 2
1 3
1 0
0 2
0 3
|
2.00000000000000000000
|
|
3
|
7
1 2
1 3
2 4
2 5
3 6
3 7
1 1
1 1
1 1
1 1
1 1
1 1
1 1
|
4.04081632653
|