← 返回题目列表

Codeforces · 235/D

D. 图形游戏

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

在计算机科学中,有一种称为“按节点分而治之”的方法来解决有关树上路径的一些难题。我们按功能描述一下这个方法是如何工作的:

solve(t)(t是一棵树):

1.在树t中选择一个节点x(通常选择权重中心)。我们将此步骤称为“A 行”。
2. 处理所有经过x的路径。
3.然后从树t中删除x。
4. 之后 t 变成一些子树。
5. 对每个子树应用求解。

当 t 只有一个节点时结束,因为删除它后,什么也没有了。

现在,WJMZBMR 错误地认为选择“A 线”中的任何节点都可以。所以他会随机选择一个节点。更糟糕的是,他认为“树”应该具有相同数量的边和节点!所以这个过程就变成这样了。

让我们定义变量totalCost。最初,totalCost 的值等于 0。因此,solve(t)(现在 t 是一个图):

1. 总成本 = 总成本 + (t 的大小)。操作“=”表示赋值。 (Size of t) 表示 t 中的节点数。
2. 随机选择图 t 中的节点 x(在 t 的所有节点中均匀选择)。
3. 然后从图 t 中删除 x。
4. 之后 t 成为一些连通分量。
5. 对每个组件应用求解。

他将在具有 n 个节点和 n 个边的连通图上应用求解。他认为这会很快见效,但其实很慢。所以他想知道这个过程的总成本的期望。你能帮助他吗?

输入

第一行包含一个整数 n (3 ≤ n ≤ 3000) — 图中节点和边的数量。接下来的 n 行中的每一行都包含两个空格分隔的整数 ai, bi (0 ≤ ai, bi ≤ n - 1),表示节点 ai 和 bi 之间的边。

考虑图节点的编号从 0 到 (n - 1)。保证该图中不存在自环、不存在重边。保证图是连通的。

输出

打印一个实数——totalCost 的期望。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

示例

输入 #1

5
3 4
2 3
2 4
0 4
1 2

输出 #1

13.166666666666666

输入 #2

3
0 1
1 2
0 2

输出 #2

6.000000000000000

输入 #3

5
0 1
1 2
2 0
3 0
4 1

输出 #3

13.166666666666666

注意

考虑第二个例子。无论我们首先选择什么,totalCost 始终是 3 + 2 + 1 = 6。