Barney 住在 USC 国家(美国查尔泽)。 USC 有 n 个城市,编号从 1 到 n,城市之间有 n - 1 条道路。南加州大学的城市和道路形成一棵有根的树(巴尼不确定它为什么有根)。树的根是1号城市。因此,如果一个人从1号城市开始他的旅程,他可以沿着道路访问任何他想要的城市。
某个女孩偷走了巴尼的心,巴尼想找到她。他开始在树的根部寻找(因为他是 Barney Stinson,而不是随机的人),他使用随机 DFS 在城市中进行搜索。该算法的伪代码如下:
如前所述,Barney 将从树根开始他的旅程(相当于调用 dfs(1))。
现在Barney需要收拾背包,所以他想更多地了解他即将到来的旅程:对于每个城市i,Barney想知道starting_time[i]的期望值。他是琼恩·雪诺的朋友,一无所知,这就是他向你寻求帮助的原因。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 105) — USC 中的城市数量。
第二行包含 n - 1 个整数 p2, p3, ..., pn (1 ≤ pi < i),其中 pi 是树中 i 号城市的父城市编号,表示 USC 中 pi 号城市和 i 号城市之间有一条道路。
输出
在输出的第一行也是唯一一行打印n个数字,其中第i个数字是starting_time[i]的预期值。
如果您对每个城市的答案的绝对或相对误差不超过 10 - 6,则将被视为正确。
示例
输入 #1
7 1 2 1 1 4 4
输出 #1
1.0 4.0 5.0 3.5 4.5 5.0 5.0
输入 #2
12 1 1 2 2 4 4 3 3 1 10 8
输出 #2
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0