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 构造一个新的无向图 $G$，它有 $N_1\cdot N_2\cdots N_K$ 个顶点，每个顶点用一个 $K$ 元组 $(j_1,j_2,\ldots,j_K)$ 标号，其中 $1\le j_i\le N_i$。在 $G$ 中，两个顶点 $(j_1,j_2,\ldots,j_K)$ 与 $(k_1,k_2,\ldots,k_K)$ 之间有一条边，当且仅当对所有 $1\le i\le K$，$j_i$ 与 $k_i$ 在 $G_i$ 中由一条边相连。

定义 $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$ 取模。

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

4

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$ 包含 $2\cdot 4=8$ 个顶点，其中有 $4$ 个与顶点 $(1,1)$ 不连通。与 $(1,1)$ 的距离为 $1$ 的顶点有 $2$ 个，距离为 $2$ 的顶点有 $1$ 个。因此答案为 $2\cdot 1+1\cdot 2=4$。

$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 没有额外限制。

题目作者：Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum