CF1060F Shrinking Tree

给定一棵 $T$（即无环连通图），有 $n$ 个顶点，编号为 $1$ 到 $n$。我们对 $T$ 进行如下操作：当 $T$ 中顶点数大于 $1$ 时，重复以下步骤： - 等概率随机选择 $T$ 的一条边； - 收缩所选边：若该边连接顶点 $v$ 和 $u$，则删除 $v$ 和 $u$，新建一个顶点，并使其与所有原本与 $v$ 或 $u$ 相邻的顶点相连。新顶点的编号等概率地取 $v$ 或 $u$ 的编号。 当操作结束时，$T$ 只剩下一个顶点，其编号为 $1, 2, \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$ 到 $n$ 成为最终唯一顶点编号的概率。每个概率要求相对或绝对误差不超过 $10^{-6}$。

在第一个样例中，最终顶点编号为 $1$ 当且仅当所有三条边的编号 $1$ 都被保留，因此概率为 $1/2^3 = 1/8$。其余编号由于对称性，概率相等，因此每个概率为 $(1 - 1/8) / 3 = 7/24$。 由 ChatGPT 4.1 翻译