小G的树

【问题描述】

小G是一个热爱生活的人，现在他在自己的家里种了一棵tree，小G亲 切地称他为G − T ree，简称GT。

我们可以形象地用N个点和N − 1条边来 描述这条边，它的形态就等同于OI中的树，其中每条边的长度为1。

随着GT一天一天地成长，它的枝干变得越发粗壮了。由于自♂然的因素，对于这N − 1条边，每一条边都有$1/2$由长度1变成长度2。

小G现在思考一个有趣的问题，他想知道这棵树直径的期望是多少呢？

【输入格式】

从文件 gtree.in 中读入数据。

第一行，包含一个数，表示N。

接下来N − 1行，每行包含两个数，描述树上的一条边。

【输出格式】

输出到文件 gtree.out 中。

一共一行，表示树的直径的期望，如果你的答案和标准答案绝对误差 或者相对误差不超过0.000001，则视为正确。

【样例输入1】

5

1 2

2 3

3 4

4 5

【样例输出1】

6

【样例输入2】

4

1 2

1 3

1 4

【样例输出2】

3.375

【样例输入3】

10

1 2

1 3

1 4

2 5

3 6

4 7

6 8

7 9

9 10

【样例输出3】

10.53125

【数据规模】

前五个点n = 15,后五个点n = 20

【时空限制】

1s，128MB