8109: USACO 2021 January Contest, Platinum Problem 1. Sum of Distances
[Creator : ]
Description
Bessie has a collection of connected, undirected graphs $G_1,G_2,…,G_K\ (2≤K≤5⋅10^4)$. For each 1≤i≤K, $G_i$ has exactly $N_i\ (N_i≥2)$ vertices labeled $1…N_i$ and $M_i\ (M_i≥N_{i−1})$ edges. Each $G_i$ may contain self-loops, but not multiple edges between the same pair of vertices.
Now Elsie creates a new undirected graph G with $N_1⋅N_2⋯N_K$ vertices, each labeled by a K-tuple $(j_1,j_2,…,j_K)$ where $1≤j_i≤N_i$. In G, two vertices $(j_1,j_2,…,j_K)$ and $(k_1,k_2,…,k_K)$ are connected by an edge if for all 1≤i≤K, $j_i$ and $k_i$ are connected by an edge in $G_i$.
Define the distance between two vertices in G that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex (1,1,…,1) and every vertex in the same component as it in G, modulo $10^9+7$.
Define the distance between two vertices in G that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex (1,1,…,1) and every vertex in the same component as it in G, modulo $10^9+7$.
Input
The first line contains K, the number of graphs.
Each graph description starts with $N_i$ and $M_i$ on a single line, followed by $M_i$ edges.
Consecutive graphs are separated by newlines for readability. It is guaranteed that $\sum N_i≤10^5$ and $\sum M_i≤2⋅10^5$.
Consecutive graphs are separated by newlines for readability. It is guaranteed that $\sum N_i≤10^5$ and $\sum M_i≤2⋅10^5$.
Output
The sum of the distances between vertex (1,1,…,1) and every vertex that is reachable from it, modulo $10^9+7$.
Sample 1 Input
2
2 1
1 2
4 4
1 2
2 3
3 4
4 1
Sample 1 Output
4
G contains 2⋅4=8 vertices, 4 of which are not connected to vertex (1,1). There are 2 vertices that are distance 1 away from (1,1) and 1 that is distance 2 away. So the answer is 2⋅1+1⋅2=4.
Sample 2 Input
3
4 4
1 2
2 3
3 1
3 4
6 5
1 2
2 3
3 4
4 5
5 6
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
Sample 2 Output
706
G contains 4⋅6⋅7=168 vertices, all of which are connected to vertex (1,1,1). The number of vertices that are distance i away from (1,1,1) for each i∈[1,7] is given by the i-th element of the following array: [4,23,28,36,40,24,12].