| VK Cup 2016 - Раунд 3 |
|---|
| Закончено |
Лимак — это маленький медвежонок гризли. Однажды он нападёт на страну оленей, но пока что он занимается уничтожением деревьев в компьютерной ролевой игре. Лимак начинает с дерева, состоящего из одной вершины. Эта вершина имеет индекс 1 и является корнем дерева.
Время от времени игра выбирает некоторое поддерево, и Лимак атакует его. Когда Лимак атакует поддерево, он разрушает каждое его ребро независимо с вероятностью 
. Штрафом Лимака после атаки на поддерево является целое число, равное высоте поддерева после атаки. Высотой поддерева называется самый длинный простой путь, начинающийся в корне поддерева и заканчивающийся в какой-нибудь вершине поддерева.
Вам требуется обрабатывать запросы двух типов.
- 1 v обозначает запрос первого типа. В дерево добавляется новая вершина, и её родителем является вершина v. Вершина получает минимальный свободный индекс (таким образом, вершины получают номера 2, 3, ...).
- 2 v обозначает запрос второго типа. Предположим, Лимак атакует поддерево вершины v. Чему в таком случае равно математическое ожидание штрафа, который он получит?
В запросах второго типа только предполагается, что Лимак атакует поддерево, но на самом деле никакие рёбра не разрушаются, и этот запрос никак не влияет на последующие.
В первой строке входных данных записано целое число q (1 ≤ q ≤ 500 000) — количество запросов.
Затем следуют q строк. В i-й из них записаны два целых числа typei и vi (1 ≤ typei ≤ 2). Если typei = 1, то vi означает предка новой вершины, а если typei = 2, то требуется вывести ответ для поддерева, корнем которого является vi.
Гарантируется, что будет хотя бы один запрос второго типа, то есть выходные данные не будут пустыми.
Также гарантируется, что к моменту поступления i-го запроса вершина vi уже существует.
Для каждого запроса второго типа выведите одно вещественное число — математическое ожидание штрафа Лимака после атаки на соответствующее поддерево. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
7
1 1
1 1
2 1
1 2
1 3
2 2
2 1
0.7500000000
0.5000000000
1.1875000000
8
2 1
1 1
1 2
1 3
1 4
2 1
1 4
2 1
0.0000000000
0.9375000000
0.9687500000
На рисунке ниже представлен первый пример. Красными кружочками обозначены запросы второго типа.
