← 返回题目列表

Codeforces · 1060/F

F. 缩小的树

中文机器翻译题面 查看原题

考虑一棵树 $$$T$$$(即,没有循环的连通图),其中 $$$n$$$ 顶点标记为 $$$1$$$ 到 $$$n$$$。我们从 $$$T$$$ 开始以下过程:当 $$$T$$$ 有多个顶点时,执行以下操作:

- 等概率地选择 $$$T$$$ 的随机边;
- 缩小所选边:如果边连接顶点 $$$v$$$ 和 $$$u$$$,则擦除 $$$v$$$ 和 $$$u$$$ 并创建一个与先前与 $$$v$$$ 或 $$$u$$$ 相邻的所有顶点相邻的新顶点。新顶点等概率地标记为 $$$v$$$ 或 $$$u$$$。

在该过程结束时,$$$T$$$ 由一个标有数字 $$$1、\ldots、n$$$ 之一的顶点组成。对于每个数字,该数字成为最终顶点标签的概率是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$)。

以下 $$$n - 1$$$ 行描述树的边缘。每行都包含两个整数 $$$u_i, v_i$$$ - 由相应边连接的顶点标签 ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$)。保证给定的图是一棵树。

输出

打印 $$$n$$$ 浮点数 - 分别是标签 $$$1、\ldots、n$$$ 所需的概率。所有数字的相对或绝对精度均应正确,最高可达 $$$10^{-6}$$$。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

0.1250000000
0.2916666667
0.2916666667
0.2916666667

输入 #2

7
1 2
1 3
2 4
2 5
3 6
3 7

输出 #2

0.0850694444
0.0664062500
0.0664062500
0.1955295139
0.1955295139
0.1955295139
0.1955295139

注意

在第一个样本中,当且仅当对于所有三个边标签 1 都存在时,生成的顶点具有标签 1,因此概率为 $$$1/2^3 = 1/8$$$。由于对称性,所有其他标签具有相同的概率,因此每个标签的概率为 $$$(1 - 1/8) / 3 = 7/24$$$。