CF696B Puzzles

Barney 生活在 USC（Charzeh 联邦）。USC 有 $n$ 个城市，编号为 $1$ 到 $n$，以及 $n-1$ 条连接它们的道路。USC 的城市和道路组成了一棵有根树（Barney 不确定为什么要有根）。树的根是编号为 $1$ 的城市。因此，如果一个人从城市 $1$ 出发，只要沿着道路前进，就能到达任意一个城市。 Barney 喜欢的女孩把他的心偷走了，他想去找她。他从树的根节点开始搜索（毕竟他是 Barney Stinson，不是 random guy），他采用了一种随机的深度优先遍历（DFS）在所有城市中搜索。该算法的伪代码如下： ```plain 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) ``` 如前所述，Barney 会从树的根节点开始他的旅程（即等价于调用 dfs(1)）。 现在 Barney 需要收拾背包，他希望更好地了解即将到来的旅程：对于每个城市 $i$，Barney 想知道 starting\_time\[i\] 的期望值。由于他是 Jon Snow 的朋友，一无所知，所以希望你帮助他解决这个问题。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示 USC 的城市数量。 第二行包含 $n-1$ 个整数 $p_2, p_3, ..., p_n$（$1 \leq p_i < i$），其中 $p_i$ 表示城市 $i$ 在树中的父亲节点编号，意味着 USC 中在城市 $p_i$ 和 $i$ 之间存在道路。

仅输出一行，包含 $n$ 个数字，其中第 $i$ 个数字表示 starting\_time\[i\] 的期望值。 对于每个城市，你的输出将被认为是正确的，当且仅当它的绝对或相对误差不超过 $10^{-6}$。

由 ChatGPT 5 翻译