Limak 是一只小灰熊。他曾经会攻击鹿国,但现在他只能在角色扮演游戏中摧毁树木。 Limak 从一棵有一个顶点的树开始。唯一的顶点索引为 1,并且是树的根。
有时,游戏会选择一个子树并允许 Limak 攻击它。当子树受到攻击时,其每条边都会以 $$\frac{1}{2}$$ 的概率被破坏,与其他边无关。然后,Limak 受到惩罚——一个等于攻击后子树高度的整数。高度定义为子树的根和子树中的任何顶点之间的路径上的最大边数。
您必须处理两种类型的查询。
- 1 v 表示第一类型的查询。出现一个新顶点,其父顶点为 v。新顶点具有下一个可用索引(因此,新顶点将编号为 2、 3、 ...)。
- 2 v 表示第二类型的查询。我们假设游戏允许 Limak 攻击以 v 为根的子树。那么,Limak 在攻击后得到的惩罚的期望值是多少?
在第二种类型的查询中,Limak 实际上并不攻击子树,因此该查询不会影响下一个查询。
输入
输入的第一行包含一个整数 q (1 ≤ q ≤ 500 000) — 查询数。
然后是 q 行。其中第 i 个包含两个整数 typei 和 vi (1 ≤ typei ≤ 2)。如果 typei = 1,则 vi 表示新顶点的父顶点,而如果 typei = 2,则应打印以 vi 为根的子树的答案。
保证至少有1次第二类查询,即输出不会为空。
保证在第 i 个查询之前顶点 vi 已经存在。
输出
对于第二种类型的每个查询,打印一个实数——如果 Limak 攻击给定子树,则惩罚的预期值。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
7 1 1 1 1 2 1 1 2 1 3 2 2 2 1
输出 #1
0.7500000000 0.5000000000 1.1875000000
输入 #2
8 2 1 1 1 1 2 1 3 1 4 2 1 1 4 2 1
输出 #2
0.0000000000 0.9375000000 0.9687500000
注意
下面,您可以看到第一个示例的绘图。红色圆圈表示第二种类型的查询。