#P4168. [2015年湖南省队省队集训]幻想乡的地图

    ID: 3383 传统题 2000ms 512MiB 尝试: 17 已通过: 4 难度: 9 上传者: 标签>难度分类省选/NOI-概率与期望期望线性性组合数学贡献法容斥原理图论基环树拆环树算法点分治点分治容斥去重多项式与生成函数卷积转化FFTCF2800

[2015年湖南省队省队集训]幻想乡的地图

[2015 湖南省队集训] 幻想乡的地图

题目描述

辉夜曾是住在月宫的公主。她找出一张幻想乡的地图,与永琳玩捉迷藏。地图是一张有 nn 个点、nn 条边的无向连通图。游戏开始时,辉夜从所有点中等概率选出一个点 vv,藏在那里。

每轮游戏,永琳从当前地图上仍存在的点中等概率选一个点 xx。若 x=vx=v,游戏结束;否则辉夜会告诉永琳所有满足下述条件的点 yy:当前图中,从 vv 到 yy 的每一条路径都包含 xx。永琳从地图上删去 xx 和这些已经排除的点,以及与它们相连的边,再开始下一轮。删除后的点不能再被选择或经过。

求永琳找到辉夜所需轮数的期望,找到辉夜的那一轮也计入。

输入格式

第一行一个正整数 nn。接下来 nn 行,每行两个整数 x,yx,y(1≤x,y≤n1\le x,y\le n),表示地图上的一条无向边。

输出格式

输出一行一个实数,表示答案。允许绝对误差不超过 10−510^{-5}。

样例 #1

样例输入 #1

3
1 2
2 3
1 3

样例输出 #1

2.000000

样例说明

在该图中,任意一个未猜中的点都不会额外排除其他点。游戏在第 11、22、33 轮结束的概率均为 13\tfrac13,因此期望为 13×1+13×2+13×3=2\tfrac13\times1+\tfrac13\times2+\tfrac13\times3=2。

数据规模与约定

全部数据满足 n≤105n\le10^5,环的长度不超过 1010。对于任意点 xx 和任意固定长度,最短路经过 xx 且长度为该固定值的点对数不超过 10910^9。

原题共有 1010 个测试点:第 11 至 22 点满足 n≤3 000n\le3\,000;第 33 点满足 n≤30 000n\le30\,000,且最长简单路径长度不超过环的长度;第 44 至 55 点满足 n≤105n\le10^5,数据随机生成。原题前 55 点时限为 11 秒,其余为 33 秒。