复杂度（complexity）

题目描述

给定人民群众喜闻乐见的树的点分治步骤如下：

Algorithm 1 {
    f(component)
        total ← total + |component|
        选择一个与 component 连通的点 u
        删除点 u，产生若干个连通块
        对于这若干个连通块，调用 f 递归处理
}

对于 $u$ 的选择，我们一般选择 $component$ 的重心，也就是删掉 $u$ 之后使得最大连通块最小。

考虑随机点分治，也就是每次随机选择 $component$ 内的任意一个点。求随机点分治的期望时间复杂度，也就是 $total$ 的期望大小。

输入格式

第一行一个数 $n$，表示树的大小。

接下来 $n-1$ 行，每行两个数 $u,v$，表示一条 $u$ 到 $v$ 的边。

输出格式

输出一行一个数，表示对于这棵树，随机点分治的期望时间复杂度。你的答案正确，当且仅当与标准答案的相对误差或绝对误差不超过 $10^{-9}$。

样例输入

3
1 2
2 3

样例输出

5.666666666

样例解释

对于任意一棵大小为 $2$ 的树，随机点分治的复杂度总是 $3$。

对于样例中给定的树，如果一开始选择 $1$ 或 $3$，则生成一棵大小为 $2$ 的树，期望时间复杂度为：

如果选择 $2$，则生成两棵大小为 $1$ 的树，期望时间复杂度为：

所以对于整棵树来说，期望时间复杂度为：

数据范围