题目描述

有一棵树，共有 $N\ (1\le n\le 10^5)$ 个节点，他会使用下列 $\tt DFS$ 算法对该树进行遍历。

starting_time 是一个容量为 n 的数组
current_time = 0
    dfs(v):
    current_time = current_time + 1
    starting_time[v] = current_time
    将 children[v] 的顺序随机排列（每个排列的概率相同）
    // children[v] 表示 v 的直接儿子组成的数组
    for u in children[v]:
        dfs(u)

$1$ 是这棵树的根，Bob 会从 $1$ 出发，即运行 dfs(1)，现在他想知道每个点 starting_time 的期望值。

输入格式

第一行一个整数 $n$，$n\le 10^5$。

第二行 $n-1$ 个整数 $p_2, p_3,...,p_n$，$1\le p_i< i$，表示节点 $i$ 的父节点。

输出格式

在一行中输出 $n$ 个数，表示每个节点 starting_time 的期望值，保留一位小数。

7
1 2 1 1 4 4

1.0 4.0 5.0 3.5 4.5 5.0 5.0

12
1 1 2 2 4 4 3 3 1 10 8

1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0