A90535.「USACO 2024.1 Platinum」Island Vacation

NOI/NOI+/CTSC

通过率：0%

时间限制：2.00s

内存限制：256MB

题目描述

题目来自 USACO 2024 January Contest, Platinum Problem 1. Island Vacation

Bessie 正在一个 $N$ （ $2\le N\le 10^4$ ）座岛组成的岛屿网络中度假，编号为 $1\ldots N$ ，由 $M$ 座双向通行的桥连接，每座桥连接两座岛（ $N-1\le M\le 3/2(N−1)$ ）。保证所有桥形成连通的简单图（具体地说，没有两座桥连接同一对岛屿，也没有一座桥连接一座岛到其自身）。

另外保证没有一座桥处在多于一个简单环上。一个简单环是一个不包含重复岛的环。

Bessie 从岛 $1$ 开始，按以下过程旅行。假设她目前在岛 $i$ 上，

如果不存在连接岛 $i$ 的她尚未穿过的桥，则她的度假结束。
否则，以 $p_i \pmod{10^9+7}$ 的概率，她的度假结束。
否则，在连接岛 $i$ 的所有她还没有穿过的桥中，她均匀地随机选择一座并穿过它。

对于每座岛，输出她在该岛上结束度假的概率，对 $10^9+7$ 取模。

输入格式

输入的第一行包含独立的测试用例的数量 $T$ （ $1\le T\le 10$ ）。相邻的测试用例之间以一个空行分隔。

每一个测试用例的第一行包含 $N$ 和 $M$ ，其中 $N$ 为岛的数量， $M$ 为桥的数量。输入保证所有测试用例的 $N$ 之和不超过 $10^4$ 。

第二行包含 $p_1,p_2,\ldots ,p_N$ （ $0\le p_i<10^9+7$ ）。

以下 $M$ 行描述所有的桥。第 $i$ 行包含整数 $u_i$ 和 $v_i$ （ $1\le u_i<v_i\le N$ ），表示第 $i$ 座桥连接岛 $u_i$ 和 $v_i$ 。输入保证所有桥满足上文中的限制。

输出格式

对于每个测试用例输出一行，包含在岛 $1$ 到 $N$ 的每一座岛上结束度假的概率模 $10^9+7$ 的余数，用空格分隔。

输入输出样例

输入#1

2

3 2
0 10 111111112
1 3
2 3

6 5
500000004 0 0 0 0 0
1 5
1 3
4 5
5 6
1 2

输出#1

0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334

输入#2

2

5 5
333333336 333333336 0 0 0
1 2
2 3
3 4
4 5
1 5

5 5
0 0 0 0 0
1 2
2 3
2 4
1 4
1 5

输出#2

777777784 222222224 0 0 0
0 0 333333336 0 666666672

输入#3

1

11 13
2 3 4 5 6 7 8 9 10 11 12
1 2
1 3
2 3
2 4
4 5
2 5
4 8
5 9
2 6
6 7
2 7
6 10
5 11

输出#3

133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18

说明/提示

测试点 4-5： $N\le 11$ 。
测试点 6-7：不存在简单环。
测试点 8-11：没有一座岛处在多于一个简单环上。
测试点 12-15：没有一座岛处在多于 $5$ 个简单环上。
测试点 16-19：没有一座岛处在多于 $50$ 个简单环上。
测试点 20-23：没有额外限制。

供题：Benjamin Qi

首页