CF1060F.Shrinking Tree

Consider a tree $T$ (that is, a connected graph without cycles) with $n$ vertices labelled $1$ through $n$. We start the following process with $T$: while $T$ has more than one vertex, do the following:

• choose a random edge of $T$ equiprobably;
• shrink the chosen edge: if the edge was connecting vertices $v$ and $u$, erase both $v$ and $u$ and create a new vertex adjacent to all vertices previously adjacent to either $v$ or $u$. The new vertex is labelled either $v$ or $u$ equiprobably.

At the end of the process, $T$ consists of a single vertex labelled with one of the numbers $1, \ldots, n$. For each of the numbers, what is the probability of this number becoming the label of the final vertex?

考虑一棵树 $T$（即一个无环的连通图），其 $n$ 个顶点分别标记为 $1$ 至 $n$。我们对 $T$ 执行如下过程：只要 $T$ 的顶点数大于 $1$，就重复以下步骤：

• 等概率地随机选取 $T$ 的一条边；
• 收缩所选的边：若该边连接顶点 $v$ 和 $u$，则删除 $v$ 和 $u$，并创建一个新顶点，该新顶点与原先同 $v$ 或 $u$ 中任一者相邻的所有顶点均相邻。新顶点的标签以相等概率取 $v$ 或 $u$。

该过程结束后，$T$ 仅剩一个顶点，其标签为 $1,\ldots,n$ 中的某一个数。对每个数，求其成为最终顶点标签的概率。

The first line contains a single integer $n$ ($1 \leq n \leq 50$).

The following $n - 1$ lines describe the tree edges. Each of these lines contains two integers $u_i, v_i$ — labels of vertices connected by the respective edge ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$). It is guaranteed that the given graph is a tree.

第一行包含一个整数 $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$）。保证所给图是一棵树。

Print $n$ floating numbers — the desired probabilities for labels $1, \ldots, n$ respectively. All numbers should be correct up to $10^{-6}$ relative or absolute precision.

输出 $n$ 个浮点数——分别为标签 $1, \ldots, n$ 所对应的期望概率。所有数值的相对误差或绝对误差均需控制在 $10^{-6}$ 以内。

In the first sample, the resulting vertex has label 1 if and only if for all three edges the label 1 survives, hence the probability is $1/2^3 = 1/8$. All other labels have equal probability due to symmetry, hence each of them has probability $(1 - 1/8) / 3 = 7/24$.

在第一个样例中，最终顶点的标签为 1 当且仅当三条边的标签 1 全部保留下来，因此概率为 $1/2^3 = 1/8$。由于对称性，其余所有标签出现的概率相等，故每个这样的标签的概率为 $(1 - 1/8) / 3 = 7/24$。