← 返回题目列表

Codeforces · 696/B

B. 谜题

中文机器翻译题面 查看原题

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