1631. [USACO10HOL]Driving Out the Piggies G

【题目描述】

奶牛们制造了一种随机臭弹，目的是驱赶小猪。小猪文明由 $ N (2 \leq N \leq 300) $ 个小猪城市组成，这些城市编号为 1 到 N，通过 $ M (1 \leq M \leq 44,850) $ 条双向道路连接，具体由它们的不同端点 $A_j$ 和 $B_j$ 指定 $ (1 \leq A_j \leq N; 1 \leq B_j \leq N) $。小猪城市 $1$ 总是与至少一个其他城市相连。

臭弹在小猪城市 $1$ 部署。每小时（包括第一小时），它有 $P/Q (1 \leq P \leq 1,000,000, 1 \leq Q \leq 1,000,000; P \leq Q) $ 的概率爆炸并污染它所在的城市。如果它没有爆炸，它会随机选择一条通往其他城市的道路并沿着它走，直到到达一个新城市。所有从一个城市出发的道路被选择的概率相同。

由于臭弹的随机性质，奶牛们想知道哪些城市最有可能被污染。给定小猪文明的地图以及臭弹在每个小时内爆炸的概率，计算每个城市被污染的概率。

例如，假设小猪文明由两个城市组成并且相连，臭弹从城市 $1$ 开始，每次进入一个城市时有 $\frac12$ 的概率爆炸：

1--2

我们有以下可能的臭弹路径（最后一个城市是终点城市）：

1: 1

2: 1-2

3: 1-2-1

4: 1-2-1-2

5: 1-2-1-2-1

等等。

要找到臭弹最终停留在城市 $1$ 的概率，我们可以将上述每条路径的概率相加（具体来说，就是上述列表中每一个奇数编号的路径）。选择第 $k$ 条路径的概率正好是 $(1/2)^k$ ——臭弹必须在前 $k-1$ 次不留在它的城市（每次概率为 $1-\frac12=\frac12$），然后在最后一个城市停留（概率为 $\frac12$）。

因此，我们在城市 $1$ 停留的概率由无穷级数 $\displaystyle\sum_{2∤ k}\left(\frac12\right)^k$ 表示。当我们无限地求和这些项时，最终得到的概率恰好是 $\frac23$，大约为 $0.666666667$。这意味着在城市 $2$ 停留的概率是 $\frac13$，大约为 $0.333333333$。

【输入格式】

第 $1$ 行：四个用空格分隔的整数：$N,M,P,Q$。

第 $2$ 行到第 $M+1$ 行：第 $i+1$ 行描述一条道路，包含两个用空格分隔的整数：$A_j$ 和 $B_j$。

【输出格式】

第 $1$ 行到第 $N$ 行：在第 $i$ 行，输出城市 $i$ 被摧毁的概率，格式为浮点数。绝对误差最多为 $10^{-6}$ 的答案将被接受（注意，您应该输出至少 $6$ 位小数以满足此要求）。

【样例输入】

2 1 1 2 
1 2 

【样例输出】

0.666666667 
0.333333333