Puzzles
time limit per
test 1 second
memory limit per
test 256 megabytes
input standard
input
output standard
output
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.
Input
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 p2, p3, ..., pn (1 ≤ pi < i), where pi is the
number of the parent city of city number i in the tree, meaning there is a
road between cities numbered pi and i in USC.
Output
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.
Examples
input
7
1 2 1 1 4 4
1 2 1 1 4 4
output
1.0 4.0 5.0 3.5 4.5 5.0 5.0
input
12
1 1 2 2 4 4 3 3 1 10 8
1 1 2 2 4 4 3 3 1 10 8
output
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
题目翻译：
谜题
每个测试点时间限制 1秒
每个测试点空间限制 256兆字节
输入 标准输入
输出 标准输出
巴尼住在USC (查则合众国，United States of Charzeh). USC 由 n 座城市组成，编号为1 到 n ，由 n - 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]的期望值。他是乔恩·斯诺的朋友，他什么都不懂，因此他向你求助。
输入
第一行包含一个整数 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即被认为正确。
样例
输入
7
1 2 1 1 4 4
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 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
解析
先证两个引理：
【引理1】在1~$n$的所有全排列中，数字1出现在任何一个位置的概率相等，且等于$ \frac1n$。
证明：设数字1出现在了位置$ k(k\in\left\{x\in\boldsymbol N\vert1\leqslant x\leqslant
n\right\})$，满足条件的全排列的个数$c_k=(n-1)!$，而全排列的个数$C=n!$，概率$ P(k)=\frac{(n-1)!}{n!}=\frac1n$。
【引理2】对于$ \forall n\in\boldsymbol
N\cap\lbrack2,+\infty\rbrack,\boldsymbol\;\sum_{i=1}^n\frac{\begin{pmatrix}n-1\\i-1\end{pmatrix}}{\begin{pmatrix}n\\i\end{pmatrix}}=\frac{n+1}2$
证明：设$m=n-1$，原命题转化为：$$\boldsymbol\;\sum_{i=1}^{m+1}\frac{\begin{pmatrix}m\\i-1\end{pmatrix}}{\begin{pmatrix}m+1\\i\end{pmatrix}}=\frac{m+2}2$$
$$\Leftrightarrow\boldsymbol\;\sum_{i=1}^m\frac{\begin{pmatrix}m\\i-1\end{pmatrix}}{\begin{pmatrix}m+1\\i\end{pmatrix}}+\frac{\begin{pmatrix}m\\m\end{pmatrix}}{\begin{pmatrix}m+1\\m+1\end{pmatrix}}=\frac
m2+1$$ $$\Leftrightarrow\boldsymbol\;\sum_{i=1}^m\frac{\begin{pmatrix}m\\i-1\end{pmatrix}}{\begin{pmatrix}m+1\\i\end{pmatrix}}=\frac
m2$$ $$\Leftrightarrow\boldsymbol\;\sum_{i=1}^m\frac{\displaystyle\frac{m!}{(m-i+1)!\cdot(i-1)!}}{\displaystyle\frac{(m+1)!}{(m+1-i)!\cdot
i!}}=\frac m2$$ $$\Leftrightarrow\boldsymbol\;\sum_{i=1}^m\frac{\mathbf
i}{\boldsymbol(\mathbf m\boldsymbol+\mathbf1\boldsymbol)}=\frac m2$$ $$\Leftrightarrow\frac{\displaystyle\frac{\mathbf
m\boldsymbol(\mathbf
m\boldsymbol+\mathbf1\boldsymbol)}{\mathbf2}}{\boldsymbol(\mathbf
m\boldsymbol+\mathbf1\boldsymbol)}=\frac m2$$显然成立。故原命题成立。
引理1告诉我们，当巴尼位于点$u$时，如果点$u$的子节点有$n$个，他第$i$个遍历每一个子树的概率都等于$ \frac1n$。又根据深度优先搜索的性质，巴尼必须遍历完整棵子树后才会遍历下一棵子树，也就是一旦遍历节点$v$所在的子树，发现顺序的期望将增加$ sum_v\cdot p $（$sum_v$为子树节点的总数，$p$为这种情况发生的概率）。
不妨令$n=6$我们有6种情况：第1个遍历节点$v$，第2个遍历节点$v$……第6个遍历节点$v$。为了方便讲解，设节点$u$的六个子树的节点数和分别为$a$，$b$，$c$，$d$，$e$，$f$，并假设$sum_v=f$。
情况一对期望的贡献为$ \frac16$，这个贡献是必须的，以下其余情况我们只讨论相对情况一的额外贡献。
情况二对期望的额外贡献为$ \frac16\cdot(\frac a5+\frac b5+\frac c5+\frac d5+\frac e5)$。可见情况二又细分为了5种子情况，假如即$a+b+c+d+e=s$，情况二的贡献可以写成$ \frac16\cdot(\frac s5)$。
情况三更加复杂，因为在遍历点$v$之前，有10种遍历另外2个子树的方案，额外贡献为$ \frac16\cdot(\frac{a+b+a+c+a+d+a+e+b+c+b+d+b+e+c+d+c+e+d+e}{10})$，五个字母各出现了4次，即贡献为$ \frac16\cdot(\frac{4s}{10})$。10和4是如何计算的呢？显然，它们分别等于$ \begin{pmatrix}5\\2\end{pmatrix}$，和$ \begin{pmatrix}4\\1\end{pmatrix}$。
类似地，情况四的额外贡献为$ \frac s6\cdot\frac{\displaystyle\begin{pmatrix}4\\3\end{pmatrix}}{\begin{pmatrix}5\\4\end{pmatrix}}$。
所有情况的总贡献为$\frac s6\sum_{i=1}^5\frac{\begin{pmatrix}4\\i-1\end{pmatrix}}{\begin{pmatrix}5\\i\end{pmatrix}}+1$根据引理2，这个值为$\frac
s2+1$。同时，由于节点$v$会继承其父节点$u$的期望，$p_v=\frac s2+1+p_u$。而$s=sum_u-sum_v-1$，所以$ p_v=\frac{\displaystyle sum_u-sum_v-1}{\displaystyle2}+1+p_u $。
于是，此题可以使用动态规划求解。
