Codeforces Round 172 (Div. 1) |
---|
Закончено |
У Мумиджу есть корневое дерево, состоящее из n вершин. Вершины дерева пронумерованы целыми числами от 1 до n. Корень дерева имеет номер 1. Мумиджу решил поиграть в игру на этом дереве.
Игра состоит из нескольких шагов. На каждом шаге Мумиджу выбирает одну из оставшихся вершин дерева (обозначим ее v) и удаляет из дерева все вершины поддерева с корнем в вершине v. Сама вершина v тоже удаляется. Игра заканчивается, когда в дереве не остается вершин. Другими словами, игра заканчивается после шага, на котором выбрана вершина с номером 1.
Каждый раз Мумиджу выбирает новую вершину равновероятно среди всех оставшихся вершин. Ваша задача — найти математическое ожидание количества шагов в описанной игре.
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество вершин дерева. В следующих n - 1 строках заданы ребра дерева. В i-той строке записаны целые числа ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — номера вершин, которые соединены i-тым ребром.
Гарантируется, что заданный граф является деревом.
Выведите единственное вещественное число — математическое ожидание количества шагов в описанной игре.
Ответ будет считаться правильным, если его относительная или абсолютная погрешность не превышает 10 - 6.
2
1 2
1.50000000000000000000
3
1 2
1 3
2.00000000000000000000
В первом тестовом примере возможны два случая. Первый — это сразу удалить корень, второй — удалить корень после одного шага. Таким образом, математическое ожидание количества шагов равно:
Второй пример более сложный. Два случая из трех приводят нас к задаче, эквивалентной первому тестовому примеру, третий случай — удалить корень на первом шаге. Таким образом, математическое ожидание количества шагов равно:
Название |
---|