3559. [USACO21Jan Platinum]Sum of Distances

【题目描述】

Bessie 有一些无向连通图 $G_1,G_2,\ldots,G_K$（$2\le K\le 5\cdot 10^4$）。对于每一个 $1\le i\le K$，$G_i$ 有 $N_i$（$N_i\ge 2$）个编号为 $1\ldots N_i$ 的结点与 $M_i$（$M_i\ge N_i-1$）条边。$G_i$ 可能含有自环，但同一对结点之间不会存在多条边。

现在 Elsie 用 $N_1\cdot N_2\cdots N_K$ 个结点建立了一个新的无向图 $G$，每个结点用一个 $K$ 元组 $(j_1,j_2,\ldots,j_K)$ 标号，其中 $1\le j_i\le N_i$。若对于所有的 $1\le i\le K$，$j_i$ 与 $k_i$ 在 $G_i$ 中连有一条边，则在 $G$ 中结点 $(j_1,j_2,\ldots,j_K)$ 和 $(k_1,k_2,\ldots,k_K)$ 之间连有一条边。

定义 $G$ 中位于同一连通分量的两个结点的距离为从一个结点到另一个结点的路径上的最小边数。计算 $G$ 中结点 $(1,1,\ldots,1)$ 与所有与其在同一连通分量的结点的距离之和，对 $10^9+7$ 取模。

【输入格式】

输入的第一行包含 $K$，为图的数量。

每个图的描述的第一行包含 $N_i$ 和 $M_i$，以下是 $M_i$ 条边。

为提高可读性，相邻的图之间用一个空行隔开。输入保证 $\sum N_i\le 10^5$ 以及 $\sum M_i\le 2\cdot 10^5$。

【输出格式】

输出结点 $(1,1,\ldots,1)$ 与所有该结点可以到达的结点的距离之和，对 $10^9+7$ 取模。

【样例输入1】

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

【样例输出1】

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

【样例输出2】

706

【样例说明】

【样例 1 说明】

$G$ 包含 $2\cdot 4=8$ 个结点，其中 $4$ 个结点不与结点 $(1,1)$ 连通。有 $2$ 个结点与 $(1,1)$ 的距离为 $1$，$1$ 个结点的距离为 $2$。所以答案为 $2\cdot 1+1\cdot 2=4$。

【样例 2 说明】

$G$ 包含 $4\cdot 6\cdot 7=168$ 个结点，均与结点 $(1,1,1)$ 连通。对于每一个 $i\in [1,7]$，与结点 $(1,1,1)$ 距离为 $i$ 的结点数量为下列数组中的第 $i$ 个元素：$[4,23,28,36,40,24,12]$。

【数据规模与约定】

测试点 $3-4$ 满足 $\prod N_i\le 300$。 

测试点 $5-10$ 满足 $\sum N_i\le 300$。 

测试点 $11-20$ 没有额外限制。

【来源】

USACO 一月公开赛 Platinum 组