Sum of Distances
Bessie has a collection of connected, undirected graphs G1,G2,…,GK (2≤K≤5⋅104). For each 1≤i≤K, Gi has exactly Ni (Ni≥2) vertices labeled 1…Ni and Mi (Mi≥Ni−1) edges. Each Gi may contain self-loops, but not multiple edges between the same pair of vertices.
Now Elsie creates a new undirected graph G with N1⋅N2⋯NK vertices, each labeled by a K-tuple (j1,j2,…,jK) where 1≤ji≤Ni. In G, two vertices (j1,j2,…,jK) and (k1,k2,…,kK) are connected by an edge if for all 1≤i≤K, ji and ki are connected by an edge in Gi.
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 109+7.
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.
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].
SCORING:
- Test cases 3-4 satisfy ∏Ni≤300.
- Test cases 5-10 satisfy ∑Ni≤300.
- Test cases 11-20 satisfy no additional constraints.
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains K, the number of graphs.
Each graph description starts with Ni and Mi on a single line, followed by Mi edges.
Consecutive graphs are separated by newlines for readability. It is guaranteed that ∑Ni≤105 and ∑Mi≤2⋅105.
Output Format
The sum of the distances between vertex (1,1,…,1) and every vertex that is reachable from it, modulo 109+7.