← 返回题目列表

Codeforces · 280/C

C. 树上的游戏

中文机器翻译题面 查看原题

Momiji 有一棵有根树,由 n 个节点组成。树节点由 1 到 n 的整数编号。根的编号是 1。红叶决定在这棵树上玩一个游戏。

游戏由几个步骤组成。在每一步中,Momiji 选择剩余的树节点之一(我们将其表示为 v),并从树中删除所有根位于节点 v 的子树节点。节点 v 也被删除。当树没有剩余节点时游戏结束。换句话说,游戏在选择节点号1的步骤之后结束。

每次 Momiji 在所有剩余节点中统一选择一个新节点。您的任务是找到所描述的游戏中步数的期望。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 树中的节点数。接下来的 n - 1 行包含树的边缘。第 i 行包含整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 由第 i 条边连接的节点的数量。

保证给定的图是一棵树。

输出

打印一个实数——所描述游戏中步数的期望。

如果绝对或相对误差不超过 10 - 6,则答案将被视为正确。

示例

输入 #1

2
1 2

输出 #1

1.50000000000000000000

输入 #2

3
1 2
1 3

输出 #2

2.00000000000000000000

注意

在第一个示例中,有两种情况。一种是直接去根,另一种是一步一步去根。因此预期的步骤是:

1 × (1 / 2) + 2 × (1 / 2) = 1.5

在第二个示例中,事情变得更加复杂。有两种情况减少到第一个样品,一种情况立即清洁。因此预期的步骤是:

1 × (1 / 3) + (1 + 1.5) × (2 / 3) = (1 / 3) + (5 / 3) = 2