Problem L: The end of the world

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
世界在流动?

简单的说,你可以把世界想象成许多空间的集合(n个)和连接这些空间的双向通道(n-1条),并且任意两个空间都能相互连通,于是得到一个简化版的世界。

在这个世界中,存在许多虚拟生命,任何一个虚拟生命可以进入通道到达另一个空间,它们从来不走回头路,所以世界的流动必将停止。

为了使模型更加简单,假设每个空间中都有一只虚拟生命。由于世界的对称性,它们选择任何一条通道的概率都是均等的(走过的除外)。作为一个优秀的程序员,请计算世界终结时每个空间中虚拟生命数量的期望。最后,这些期望中一定有个最大的,找到它,并且输出。

第一行有一个数n (3≤n≤100000) ,表示空间的数量(空间编号从1到n)

接下来有n-1行,每行有两个整数a,b(1≤a,b≤n),表示空间a和空间b之间存在一条通道。

以n=0结束。

输出一个数,表示世界终结时所有空间的期望值中最大的那一个。(保留三位小数)
3
1 2
1 3
4
1 2
1 3
2 4
1.500
2.000