思路

DFS 每个点 u ，当删除点 u 时，形成若干个子树 v1, v2, v3, 以及一个 u 的祖先连通块

v1，v2 和 v3 等子树的大小可以通过 DFS 获得，u 的祖先连通块大小为 n - 1 - (v1 + v2 + v3 + ...)

取所有子树以及 u 的祖先连通块大小的最大值即可

最终对于每个点删除后的最大连通块的大小累加，最后除以 n 即为期望。

题目描述

众所周知，点分治算法最重要的一个步骤是寻找一棵树的重心后删除，满足形成的森林中最大连通块尽可能小。 但很可惜，小红不会寻找树的重心，因此她会随机选择一个节点进行删除。这样就会导致最终算法的复杂度增加。小红想知道，对于一个给定的树，随机取一个点删除，形成的森林中最大连通块大小的期望是多少?

输入描述

第一行输入一个正整数$n$，代表树的节点数量 接下来的$n-1$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条边连接。

$1\le n\le 10^5$

$1\le u,v\le n$

输出描述

一个浮点数，代表最终最大连通块的大小期望。如果你的答案和标准答案的相对误差小于$10^{-6}$，则认为你的答案正确。

样例1

输入

2
1 2

输出

1.000000000

说明

无论删除的是哪个节点，形成的森林的最大连通块大小均是 1.

样例2

输入

3
1 3
2 3

输出

1.6666666666667

说明

删除1号节点时，最大连通块大小为2。
删除2号节点时，最大连通块大小为1。
删除3号节点时，最大连通块大小为2。
因此随机选一个节点删除，连通块的大小期望是5/3