2061: [USACO 2025 January Contest, Gold] Problem 2. Reachable Pairs
题目描述
Consider an undirected graph with nodes labeled and edges (). You're given a binary string . At time for each ,
- If , node is removed from the graph.
- If , node is removed from the graph, and edges are added between every pair of neighbors that node had just before removal.
Note that in both cases, when a node is removed from the graph all of its incident edges are removed as well.
Count the number of pairs of nodes that can reach each other via some sequence of edges just before each of timesteps
输入
The second line contains the bit string of length N.
The next lines each contain two integers denoting an edge of the graph.
输出
样例输入
3 2
111
1 2
1 3样例输出
3
1
0提示
Before any removals, all pairs of nodes are reachable from each other. After node 1 is removed, an edge is added between 2 and 3, so they can still reach each other.
SAMPLE INPUT:
3 2
000
1 2
1 3
SAMPLE OUTPUT:
30
0
Before any removals, all pairs of nodes are reachable from each other. After node 1 is removed, 2 and 3 can no longer reach each other.
SAMPLE INPUT:
7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 7
SAMPLE OUTPUT:
11
7
4
2
1
1
0
SCORING:
- Inputs 4-6:
- Inputs 7-8: All equal zero.
- Inputs 9-11: All equal one.
- Inputs 12-23: No additional constraints.