P7293 [USACO21JAN] Sum of Distances P

Bessie has some undirected connected graphs $G_1,G_2,\dots,G_K$ ($2 \le K \le 5 \cdot 10^4$). For each $1 \le i \le K$, $G_i$ has $N_i$ ($N_i \ge 2$) vertices numbered $1 \dots N_i$ and $M_i$ ($M_i \ge N_i - 1$) edges. $G_i$ may contain self-loops, but there are no multiple edges between the same pair of vertices. Now Elsie builds a new undirected graph $G$ with $N_1 \cdot N_2 \cdots N_K$ vertices. Each vertex is labeled by a $K$-tuple $(j_1,j_2,\dots,j_K)$, where $1 \le j_i \le N_i$. If for all $1 \le i \le K$, $j_i$ and $k_i$ are connected by an edge in $G_i$, then there is an edge in $G$ between vertices $(j_1,j_2,\dots,j_K)$ and $(k_1,k_2,\dots,k_K)$. Define the *distance* between two vertices in the same connected component of $G$ as the minimum number of edges on a path from one to the other. Compute the sum of distances from vertex $(1,1,\dots,1)$ to all vertices in the same connected component as it, modulo $10^9+7$.

The first line contains $K$, the number of graphs. The first line of each graph description contains $N_i$ and $M_i$, followed by $M_i$ edges. For readability, there is a blank line between adjacent graphs. The input guarantees that $∑N_i \le 10^5$ and $∑M_i \le 2 \cdot 10^5$.

Output the sum of distances from vertex $(1,1,\dots,1)$ to all vertices reachable from it, modulo $10^9+7$.

#### Sample 1 Explanation $G$ contains $2 \cdot 4 = 8$ vertices, and $4$ of them are not connected to vertex $(1,1)$. There are $2$ vertices at distance $1$ from $(1,1)$, and $1$ vertex at distance $2$. So the answer is $2 \cdot 1 + 1 \cdot 2 = 4$. #### Sample 2 Explanation $G$ contains $4 \cdot 6 \cdot 7 = 168$ vertices, all connected to vertex $(1,1,1)$. For each $i \in [1,7]$, the number of vertices at distance $i$ from $(1,1,1)$ is the $i$-th element of the following array: $[4,23,28,36,40,24,12]$. #### Testdata Properties - Testdata $3-4$ satisfies $∏N_i \le 300$. - Testdata $5-10$ satisfies $∑N_i \le 300$. - Testdata $11-20$ has no additional restrictions. Problem by: Benjamin Qi. Translated by ChatGPT 5