最小生成树

ID: 1289

传统题

4000ms

256MiB

难度: 8

上传者:

问题描述

给定一张含有 $n$ 个点与 $m$ 条边的带权无向简单图，每条边权要求是1到 $k$ 之间的整数。希望再加一条满足边权限制的边，使得新图是一张存在至少一个生成树的简单图，且新加的边一定在它的任何一个最小生成树里。要求计算有多少种方案，输出方案数模 $(10^9 + 7)$ 的值。

第一行包含一个整数 $T(1 \leq T \leq 10^5)$ ，表示测试用例的数量
接下来是 $T$ $T$ 个测试用例。对于每个测试用例：
- 第一行包含三个整数 $n$ 、 $m$ 和 $k$
- $1 \leq n \leq 10^5,$ $0 \leq m \leq$ $\min(2 \times 10^5, \frac{n(n - 1)}{2}),$ $1 \leq k \leq 10^9$
- 接下来的 $m$ 行描述给定的简单图，每行包含三个整数 $u$ 、 $v$ 和 $w(1 \leq u, v \leq n, u \neq v, 1 \leq w \leq k)$ ，表示一条连接 $u$ 和 $v$ 的权重为 $w$ 的边
保证 $T$ 个测试用例中 $N$ 之和、 $M$ 之和分别不超过 $5 \times 10^5$ 和 $10^6$

对于每个测试用例，在一行中输出一个整数，表示满足要求的加边方案数模 $(10^9 + 7)$ 。