#P13765. [2019年备战北大冬令营]复杂度

    ID: 12967 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-指示变量期望线性性点分治点分治容斥去重卷积转化NTT中国剩余定理

[2019年备战北大冬令营]复杂度

给定人民群众喜闻乐见的树的点分治步骤如下:

f(component) {
    total <- total + |component|
    选择一个与component相连的点u
    删除点u后,产生若干个连通块
    对于这若干个连通块,调用f递归处理
}

对于 uu 的选择,我们一般选择 componentcomponent 的重心,也就是删除掉 uu 之后使得最大的连通块最小。

考虑随机点分治,也就是每次随机选择 componentcomponent 内的任意一个点。求随机点分治的期望时间复杂度,也就是 totaltotal 的期望大小。

输入格式

第一行一个数 n(n≤50000)n(n\le50000),表示树的大小。

接下来 n−1n-1 行,每行两个数 u,vu, v,表示一条 uu 与 vv 之间的边。

输出格式

输出一行一个实数,表示对于这棵树,随机点分治的期望时间复杂度。

你的答案正确,当且仅当与 stdstd 的相对误差或绝对误差不超过 10−910^{-9}。

Samples

9
9 5
9 6
9 7
5 2
1 3
9 1
4 8
9 4
32.8666666667