考虑一棵树 $$$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$$$。