UOJ Logo LFYZ Online Judge

LFYZOJ

#54. 【2018年2月期末欢乐赛】乡文明单位

统计

问题描述

上白泽慧音为了让寺子屋评上乡文明单位,决定对她的学生进行家访。

我们把这些地点抽象成 $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