Skip to content

1136: 旅行

题目

题目描述

新火星一共有 $n$ 个城市和 $n-1$ 条道路,每条道路连接两个城市,长度均为 $1$ , 并且通过这些道路我们可以从任何一个城市到达任何一个城市。

IcefoxXHRlyb从城市 $1$ 出发,沿着这些道路旅行,每当他们游历完一个城市后,就会选择一个与当前城市相连并且还没有去过的城市继续旅行。在每个城市,它们都会以相同的概率移动去上述符合要求的城市,并且当没有这样的城市可走时他们的旅行就结束了。请问他们这次旅行的期望长度是多少呢?

Hint: (以下截图自维基百科)

输入格式

第一行一个正整数 $n$ , 表示城市的数量。

接下来 $n-1$ 行,每行两个整数 $x,y$ , 表示一条道路连接城市 $x$ 和城市 $y$ 。

保证通过这些道路可以从任何一个城市到达任何一个城市。

输出格式

一个数,表示这次旅行长度的期望值。旅行从城市 $1$ 开始。

当你的答案的绝对或相对误差不超过 $10^{-6}$ 时你的答案将会被接受。

换句话说,假定你的答案是 $a$,标准答案是 $b$,当 $\frac{|a-b|}{max(1,b)} \leq 10^{-6}$ 时你的答案将会被接受。

样例输入

样例输入1

text 4 1 2 1 3 2 4

样例输入2

text 5 1 2 1 3 3 4 2 5

样例输出

样例输出1

text 1.500000000000000

样例输出2

text 2.000000000000000

数据范围

对于 10% 的数据,$1\leq n\leq 10$

对于 30% 的数据,$1\leq n\leq 1000$

对于 另外 20% 的数据,保证数据是一条链

对于 另外 20% 的数据,保证树是一颗以 $1$ 为根的满二叉树

对于 100% 的数据,保证 $1\leq n\leq 10^5$

说明

在第一个例子中,他们的旅行可能以同等的概率停止于城市 $3$ 或城市 $4$。去城市 $3$ 的距离是 $1$,去城市 $4$ 的距离是 $2$,所以期望是 $1.5$。

在第二个例子中,他们的旅行可能停止于城市 $4$ 或城市 $5$。去这些城市的距离都是 $2$,所以期望是 $2$ 。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!