CF643E.Bear and Destroying Subtrees

Limak is a little grizzly bear. He will once attack Deerland but now he can only destroy trees in role-playing games. Limak starts with a tree with one vertex. The only vertex has index 1 and is a root of the tree.

Sometimes, a game chooses a subtree and allows Limak to attack it. When a subtree is attacked then each of its edges is destroyed with probability , independently of other edges. Then, Limak gets the penalty — an integer equal to the height of the subtree after the attack. The height is defined as the maximum number of edges on the path between the root of the subtree and any vertex in the subtree.

You must handle queries of two types.

• 1 v denotes a query of the first type. A new vertex appears and its parent is v. A new vertex has the next available index (so, new vertices will be numbered 2, 3, ...).
• 2 v denotes a query of the second type. For a moment let's assume that the game allows Limak to attack a subtree rooted in v. Then, what would be the expected value of the penalty Limak gets after the attack?

In a query of the second type, Limak doesn't actually attack the subtree and thus the query doesn't affect next queries.

Limak 是一只小灰熊。他终将进攻鹿地（Deerland），但现在他只能在角色扮演游戏中摧毁树木。Limak 从一棵仅含一个顶点的树开始。该唯一顶点编号为 1，且是这棵树的根节点。

有时，游戏会选定一棵子树，允许 Limak 对其发动攻击。当一棵子树被攻击时，其每条边均以概率 被独立摧毁（即各边是否被摧毁相互独立）。随后，Limak 将受到惩罚——惩罚值为攻击后该子树的高度（一个整数）。此处“高度”定义为：子树根节点到其任意顶点的路径上所含边数的最大值。

你需要处理两类查询：

• 1 v 表示第一类查询：新增一个顶点，其父节点为 v；新顶点的编号取当前尚未使用的最小正整数（因此新增顶点的编号依次为 2, 3, …）。
• 2 v 表示第二类查询：假设此刻游戏允许 Limak 攻击以 v 为根的子树，则 Limak 在攻击后所受惩罚的期望值是多少？

在第二类查询中，Limak 并不会实际攻击该子树，因此该查询不会对后续查询产生任何影响。

The first line of the input contains one integer q (1 ≤ q ≤ 500 000) — the number of queries.

Then, q lines follow. The i-th of them contains two integers type__i and v__i (1 ≤ type__i ≤ 2). If type__i = 1 then v__i denotes a parent of a new vertex, while if type__i = 2 then you should print the answer for a subtree rooted in v__i.

It's guaranteed that there will be at least 1 query of the second type, that is, the output won't be empty.

It's guaranteed that just before the i-th query a vertex v__i already exists.

输入的第一行包含一个整数 $q$（$1 \le q \le 500\,000$），表示查询次数。

接下来有 $q$ 行。其中第 $i$ 行包含两个整数 $\text{type}_i$ 和 $v_i$（$1 \le \text{type}_i \le 2$）。若 $\text{type}_i = 1$，则 $v_i$ 表示一个新顶点的父节点；若 $\text{type}_i = 2$，则需输出以 $v_i$ 为根的子树的答案。

保证至少存在一次类型为 2 的查询，即输出非空。

保证在执行第 $i$ 次查询之前，顶点 $v_i$ 已经存在。

For each query of the second type print one real number —the expected value of the penalty if Limak attacks the given subtree. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if .

对于每个第二类查询，请输出一个实数——即 Limak 攻击给定子树时的罚值的期望值。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

具体而言：假设你的答案为 $a$，评测组的标准答案为 $b$。当且仅当 时，评测程序将判定你的答案正确。

Below, you can see the drawing for the first sample. Red circles denote queries of the second type.

如下所示，是第一个样例的示意图。红色圆圈表示第二类查询。