题目描述

公交车现在给你一棵树。公交车每次会随机等概率选择一未染黑的点，将它及其子树染黑。问期望多 少次操作可以将树全部染黑。

输入格式

第一行为一个整数$\red{n，}$描述这棵树有$\red{n}$个节点。

接下来$\red{n-1}$行，每行两个整数$\red{a_i}$和$\red{b_i，}$描述这个树的其中一条边的起点和终点的编号分别为$\red{a_i}$和$\red{b_i}$。

输出格式

输出一个实数，为描述的期望。

你的答案需要保留三位小数

样例

输入样例1

2
1 2

输出样例1

1.500

输入样例2

3
1 2
1 3

输出样例2

2.000

提示

在第一个示例中，有两个案例。

一个是直接删除根，另一个是在一个步骤后删除根。 因此，预期的步骤如下:

$\red{1 ×}$ $\red{(1/2) + 2 ×}$ $\red{(1/2) = 1.5}$

在第二个样本中，情况变得更加复杂。有两种情况可以减少到第一个样本，一个案例立即被清理。

因此，预期的步骤如下：

$\red{1 ×}$ $\red{(1/3) + (1 + 1.5) ×}$ $\red{(2/3) = (1/3) + (5/3) = 2}$