P17418 [ICPC 2018 Xuzhou R] Rikka with Minimum Spanning Trees

大家好！我是你们的老朋友 Rikka。欢迎来到徐州。这是第一题，一道关于最小生成树（MST）的题目。我向你们保证，对大多数人来说这应该是 **最简单的问题**。 最小生成树，或称最小权重生成树，是从边带权无向图中选出的一个边子集，它们构成一棵树，能够在没有任何环的情况下以最小的总边权连接所有顶点。 在本题中，Rikka 想让你计算给定图的所有生成树的总边权之和，显然，这等于单棵最小生成树的总边权乘以不同最小生成树的总数。注意，若两棵生成树的边集不同，则认为它们是不同的生成树。此外，一个不连通的图可能没有生成树，此时不同生成树的数量为零。 为了减小输入规模，Rikka 通过一个给定随机种子的随机数生成器来提供一个边带权无向图，随机种子用两个整数 $k_1$ 和 $k_2$ 表示。假设图的顶点数和边数分别为 $n$ 和 $m$，下面的 C++ 代码将展示如何生成该图，并将第 $i$ 条边（连接顶点 $u[i]$ 和 $v[i]$，权重为 $w[i]$）存入相应数组。你可以直接在提交中使用该代码。 ```cpp unsigned long long k1, k2; unsigned long long xorShift128Plus() { unsigned long long k3 = k1, k4 = k2; k1 = k4; k3 ^= k3 > 17) ^ (k4 >> 26); return k2 + k4; } int n, m, u[100001], v[100001]; unsigned long long w[100001]; void gen() { scanf("%d%d%llu%llu", &n, &m, &k1, &k2); for(int i = 1; i

输入包含多组测试数据，第一行是一个整数 $T$（$1 \le T \le 100$），表示测试数据的组数。 对于每组测试数据，仅有一行四个整数 $n$（$1 \le n \le 10^5$），$m$（$m = 10^5$），$k_1$ 和 $k_2$（$10^8 \le k_1, k_2 \le 10^{12}$），其中 $k_1$ 和 $k_2$ 是随机选定的（样例除外）。

对于每组测试数据，输出一行一个整数，即答案对 $(10^9 + 7)$ 取模的结果。

由于生成器代码仅提供 C++ 版本，Rikka 强烈建议你们使用 C 或 C++ 来解决本题，而非其他编程语言。 翻译由 DeepSeek V4 Pro 完成