#P3451. Tyvj1953 Normal

    ID: 2651 传统题 1000ms 512MiB 尝试: 671 已通过: 228 难度: 8 上传者: 标签>CF2500提高+/省选-指示变量期望线性性点分治点分治容斥去重卷积转化NTT

Tyvj1953 Normal

题目描述

某天 WJMZBMR 学习了一个神奇的算法:树的点分治!

这个算法的核心是这样的:

time = 0
Solve(Tree a) {
  time += a.size;
  if (a.size == 1) return;
  else {
    select x in a;
    delete a[x];
  }
}
消耗时间 = 0
Solve(树 a)
  消耗时间 += a 的大小
  如果 a 中 只有 1 个点
    退出
  否则
    在 a 中选一个点x
    在 a 中删除点x

那么 aa 变成了几个小一点的树,对每个小树递归调用 SolveSolve

我们注意到的这个算法的时间复杂度跟选择的点 xx 是密切相关的,如果 xx 是树的重心,那么时间复杂度就是 O(nlogn)O(nlogn)

但是由于 WJMZBMR 比较傻逼,他决定随机在 aa 中选择一个点作为 xx,Sevenkplus 告诉他这样做的最坏复杂度是 O(n2)O(n^2),但是 WJMZBMR 就是不信,于是 Sevenkplus 花了几分钟写了一个程序证明了这一点,你也试试看吧。

现在给你一颗树,你能告诉 WJMZBMR 他的傻逼算法需要的期望消耗时间吗?(以给出的 SolveSolve 函数中的为标准)

输入格式

第一行一个整数 nn,表示树的大小; 接下来 n−1n-1 行每行两个数 a,ba,b,表示 aa 和 bb 之间有一条边。

输出格式

一行一个浮点数表示答案,并四舍五入到小数点后4位

3
0 1
1 2
5.6667

数据范围

对于 100100% 的数据,n≤30000n\leq 30000;

树的节点从 00 开始编号。

题目来源

我们都爱GYZ杯