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