TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4576
  • 题目
  • P4576Normal
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    评测说明 : 1s,128m
    问题描述

    某天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里面的那个为标准)

    输入格式

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

    输出格式

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

    样例输入 1

    3
    0 1
    1 2

    样例输出 1

    5.6667

    样例输入 2

    10
    0 1
    0 2
    0 3
    0 4
    2 5
    1 6
    5 7
    7 8
    5 9

    样例输出 2

    37.1524

    提示

    n<=30000


    来源  bzoj 3451