#2799. Tyvj1953 Normal

Tyvj1953 Normal

Description

某天WJMZBMR学习了一个神奇的算法:树的点分治! 这个算法的核心是这样的: 消耗时间=0 Solve(树 a) 消耗时间 += a 的 大小 如果 a 中 只有 1 个点 退出 否则在a中选一个点x,在a中删除点x 那么a变成了几个小一点的树,对每个小树递归调用Solve 我们注意到的这个算法的时间复杂度跟选择的点x是密切相关的。 如果x是树的重心,那么时间复杂度就是O(nlogn) 但是由于WJMZBMR比较傻逼,他决定随机在a中选择一个点作为x! Sevenkplus告诉他这样做的最坏复杂度是O(n^2) 但是WJMZBMR就是不信><。。。 于是Sevenkplus花了几分钟写了一个程序证明了这一点。。。你也试试看吧^^ 现在给你一颗树,你能告诉WJMZBMR他的傻逼算法需要的期望消耗时间吗?(消耗时间按在Solve里面的那个为标准)

Format

Input

第一行一个整数n,表示树的大小 接下来n-1行每行两个数a,b,表示a和b之间有一条边 注意点是从0开始标号的

Output

一行一个浮点数表示答案 四舍五入到小数点后4位 如果害怕精度跪建议用long double或者extended

Samples

3
0 1
1 2
5.6667

Limitation

n<=30000