#73py23. Game on Tree

时间限制：1 s       空间限制：250 MiB       标签： CodeForces 缺题解 

算法难度等级：0       思维难度等级：0       实现难度等级：0

题目描述

给定一棵有根树，结点编号从 $1$ 到 $n$。根结点为 $1$ 号结点。

对于每一次操作，等概率的选择一个尚未被删去的结点并将它及其子树全部删去。当所有结点被删除之后，游戏结束；也就是说，删除 $1$ 号结点后游戏即结束。

要求求出删除所有结点的期望操作次数。

输入格式

第一行，一个正整数 $n$ 表示结点数量。

接下来 $n-1$ 行每行两个数，表示树上的一条连接 $a_i$ 与 $b_i$ 的边 $(a_i,b_i)$

保证给定的数据是一棵树。

输出格式

输出一个实数，表示期望操作次数。答案误差在 $10^{-6}$ 之内则认为正确。

2
1 2

1.50000000000000000000

3
1 2
1 3

2.00000000000000000000

样例解释

在第一个样例中，有两种情况：

一种是直接删除根（即 $1$ 号结点），另一种是先删去 $2$ 号结点，再删除 $1$ 号结点。

操作次数的期望是 $1\times \dfrac12+2\times\dfrac12=1.5$。

在第二个样例中，情况更为复杂。其中有两种情况会将问题转化成第一个样例，而剩下的一种情况会一次全部删除。

操作次数的期望是 $1\times\dfrac13+(1+1.5)\times\dfrac23=\dfrac13+\dfrac53=2$。