CF235D Graph Game

在计算机科学中，有一种称为“按点分治”（Divide And Conquer By Node）的方法，用于解决一些关于树上路径的难题。让我们通过如下函数描述该方法： $ solve(t) $（$ t $ 是一棵树）： 1. 在树 $ t $ 中选择一个节点 $ x $（通常选择“重心”）。我们把这一步称为“步骤A”。 2. 处理所有经过 $ x $ 的路径。 3. 从树 $ t $ 中删除 $ x $。 4. 此时 $ t $ 变成一些子树。 5. 对每棵子树递归调用 $ solve $。 当 $ t $ 只剩一个节点时过程结束，因为删掉它之后就什么也没有了。 现在，WJMZBMR 错误地认为在“步骤A”中选任意一个节点都可以，所以他会随机选择一个节点。此外，更糟糕的是，他认为“树”应该有与节点数相等的边数！于是该过程变成了如下形式： 我们定义变量 $ totalCost $，其初始值为 $ 0 $。现在 $ solve(t) $（此时 $ t $ 是一张图）定义为： 1. $ totalCost = totalCost + (|t|) $。操作“=”表示赋值，$ |t| $ 表示 $ t $ 中的节点数。 2. 随机（等概率）选择图 $ t $ 中的一个节点 $ x $。 3. 从图 $ t $ 中删除 $ x $。 4. 此时 $ t $ 变成若干连通分量。 5. 对每个连通分量递归调用 $ solve $。 他会在一个有 $ n $ 个节点和 $ n $ 条边的连通图上应用 $ solve $。他以为算法会很快，但实际上很慢。现在他想知道这个过程的 $ totalCost $ 的期望值。你能帮助他吗？

第一行包含一个整数 $ n $（$ 3 \leq n \leq 3000 $）——图中的节点数和边数。接下来的 $ n $ 行，每行包含两个用空格分隔的整数 $ a_{i},b_{i} $（$ 0 \leq a_{i},b_{i} \leq n-1 $），表示一条连接 $ a_{i} $ 和 $ b_{i} $ 的边。 假定图的节点编号为 $ 0 $ 到 $ n-1 $。保证该图无自环、无重边，且图是连通的。

输出一个实数，表示 $ totalCost $ 的期望值。如果你的答案的绝对误差或相对误差不超过 $ 10^{-6} $，则被视为正确。

考虑第二个样例。无论第一次选择什么节点，$ totalCost $ 总是 $ 3+2+1=6 $。 由 ChatGPT 5 翻译