CF696B.Puzzles

Barney lives in country USC (United States of Charzeh). USC has n cities numbered from 1 through n and n - 1 roads between them. Cities and roads of USC form a rooted tree (Barney's not sure why it is rooted). Root of the tree is the city number 1. Thus if one will start his journey from city 1, he can visit any city he wants by following roads.

Some girl has stolen Barney's heart, and Barney wants to find her. He starts looking for in the root of the tree and (since he is Barney Stinson not a random guy), he uses a random DFS to search in the cities. A pseudo code of this algorithm is as follows:

let starting_time be an array of length n
current_time = 0
dfs(v):
current_time = current_time + 1
starting_time[v] = current_time
shuffle children[v] randomly (each permutation with equal possibility)
// children[v] is vector of children cities of city v
for u in children[v]:
dfs(u)

As told before, Barney will start his journey in the root of the tree (equivalent to call dfs(1)).

Now Barney needs to pack a backpack and so he wants to know more about his upcoming journey: for every city i, Barney wants to know the expected value of starting_time[i]. He's a friend of Jon Snow and knows nothing, that's why he asked for your help.

巴尼生活在 USC 国（Charzeh 合众国）。USC 共有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间由 $n-1$ 条道路相连。USC 的城市与道路构成一棵有根树（巴尼不确定为何这棵树是有根的）。该树的根节点为城市 $1$。因此，若从城市 $1$ 出发，沿着道路行进，便可到达任意一座城市。

某位姑娘偷走了巴尼的心，巴尼决心找到她。他从树的根节点开始寻找（即从城市 $1$ 出发），并且（由于他是巴尼·斯廷森，而非普通人）采用一种随机深度优先搜索（DFS）策略遍历各城市。该算法的伪代码如下：

令 starting_time 为一个长度为 $n$ 的数组
current_time = 0
dfs(v):
  current_time = current_time + 1
  starting_time[v] = current_time
  随机打乱 children[v]（所有排列出现概率均等）
  // children[v] 是城市 $v$ 的子节点城市组成的向量
  对 children[v] 中每个 u：
    dfs(u)

如前所述，巴尼将从树的根节点出发（即执行 dfs(1)）。

现在巴尼需要收拾背包，因此他希望更深入地了解这次旅程：对于每座城市 $i$，巴尼想知道 starting_time[i] 的期望值。作为琼恩·雪诺的朋友，他对这些一无所知，因此他向你求助。

The first line of input contains a single integer n (1 ≤ n ≤ 105) — the number of cities in USC.

The second line contains n - 1 integers _p_2, _p_3, ..., p__n (1 ≤ p__i < i), where p__i is the number of the parent city of city number i in the tree, meaning there is a road between cities numbered p__i and i in USC.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示 USC 中城市的数量。

第二行包含 $n-1$ 个整数 $p_2,\ p_3,\ \dots,\ p_n$（$1 \leq p_i < i$），其中 $p_i$ 表示城市 $i$ 在树中的父城市编号，即 USC 中城市 $p_i$ 与城市 $i$ 之间存在一条道路。

In the first and only line of output print n numbers, where i-th number is the expected value of starting_time[i].

Your answer for each city will be considered correct if its absolute or relative error does not exceed 10 - 6.

在输出的第一行且唯一一行中，输出 $n$ 个数，其中第 $i$ 个数为 $\text{starting\_time}[i]$ 的期望值。

对于每个城市的答案，若其绝对误差或相对误差不超过 $10^{-6}$，则视为正确。