问题描述
上白泽慧音为了让寺子屋评上乡文明单位,决定对她的学生进行家访。
我们把这些地点抽象成 $n$ 个点,有 $n-1$ 条无向边连接这些点,且保证这些点两两可达。寺子屋在第 1 号点。慧音从寺子屋开始移动。每次移动,她会等概率地选择一个跟她当前处在的点相连的并且没有走过的点,然后移动到那里。
假设每条边的长度是 1,请你告诉慧音,她家访的期望移动距离是多少。
如果你不知道什么是期望,请搜索“数学期望”。
输入格式
第一行一个整数 $n$,代表点的数量。
下来 $n$ 行每行两个整数 $u,v$,代表点 $u$ 和点 $v$ 之间有一条无向边。
输出格式
一个小数,是慧音家访的期望移动距离。
样例一
input
4 1 2 1 3 2 4
output
1.500000
样例二
input
5 1 2 1 3 3 4 2 5
output
2.000000
数据范围与约定
对于 $100\%$ 的数据,$n \leq 100000$。
你的答案会被接受当且仅当你的答案和标准答案误差小于 $10^{-5}$。
时间限制: $1\mathrm{s}$
内存限制: $256\mathrm{MB}$
来源
cf 839c