#PU1092. USACO 2021 January Contest, Platinum — Problem 1. Sum of Distances

    ID: 1482 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan21来源:usaco.orgscoring:equal_test_cases并查集

USACO 2021 January Contest, Platinum — Problem 1. Sum of Distances

USACO 2021 January Contest, Platinum — Problem 1. Sum of Distances

题目描述

Bessie has a collection of connected, undirected graphs G1,G2,…,GKG_1,G_2,\ldots,G_K (2≤K≤5⋅1042\le K\le 5\cdot 10^4). For each 1≤i≤K1\le i\le K, GiG_i has exactly NiN_i (Ni≥2N_i\ge 2) vertices labeled 1…Ni1\ldots N_i and MiM_i (Mi≥Ni−1M_i\ge N_i-1) edges. Each GiG_i may contain self-loops, but not multiple edges between the same pair of vertices. Now Elsie creates a new undirected graph GG with N1⋅N2⋯NKN_1\cdot N_2\cdots N_K vertices, each labeled by a KK-tuple (j1,j2,…,jK)(j_1,j_2,\ldots,j_K) where 1≤ji≤Ni1\le j_i\le N_i. In GG, two vertices (j1,j2,…,jK)(j_1,j_2,\ldots,j_K) and (k1,k2,…,kK)(k_1,k_2,\ldots,k_K) are connected by an edge if for all 1≤i≤K1\le i\le K, jij_i and kik_i are connected by an edge in GiG_i. Define the distance between two vertices in GG 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)(1,1,\ldots,1) and every vertex in the same component as it in GG, modulo 109+710^9+7.

输入格式

The first line contains KK, the number of graphs. Each graph description starts with NiN_i and MiM_i on a single line, followed by MiM_i edges. Consecutive graphs are separated by newlines for readability. It is guaranteed that ∑Ni≤105\sum N_i\le 10^5 and ∑Mi≤2⋅105\sum M_i\le 2\cdot 10^5.

输出格式

The sum of the distances between vertex (1,1,…,1)(1,1,\ldots,1) and every vertex that is reachable from it, modulo 109+710^9+7.

数据范围

Test cases 3-4 satisfy ∏Ni≤300\prod N_i\le 300. Test cases 5-10 satisfy ∑Ni≤300\sum N_i\le 300. Test cases 11-20 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1
4
$G$ contains $2\cdot 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\cdot 1+1\cdot 2=4$.

样例 2

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
706
$G$ contains $4\cdot 6\cdot 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\in [1,7]$ is given by the $i$-th element of the following
array:
$[4,23,28,36,40,24,12]$.