UOJ Logo Universal Online Judge

UOJ

#956. 【统一省选2025】岁月

附件下载 统计

希望大家一直记得我。
“希望大家永远忘了我。”

小 Y 有一个 n 个节点、m 条边的带权无向图 G,节点由 1 至 n 编号。第 i (1im) 条边连接 uivi,边权为 wi。保证 G 连通且没有重边自环。

小 Y 预见到岁月将会磨灭图 G 的痕迹,而这会导致一些边变成有向边,另一些边直接消失。具体地,图 G 历经岁月将会磨损为 n 个节点的带权有向图 G,其中对于第 i (1im) 条边,G

  • 14 的概率同时存在 uiviviui 的有向边,它们的边权均为 wi;
  • 14 的概率存在 viui、边权为 wi 的有向边,而不存在其反向边;
  • 14 的概率存在 uivi、边权为 wi 的有向边,而不存在其反向边;
  • 14 的概率 uivi 之间没有边。

所有 m 个随机事件是独立的。

小 Y 认为一个无向图的核心是最小生成树,而一个有向图的核心是最小外向生成树。称图 G 的一个边子集 E外向生成树,当且仅当 |E|=n1 且存在一个节点 x 可以只经过 E 中的有向边到达图 G 上的所有节点。图 G最小外向生成树即为图 G 上边权和最小的外向生成树。

小 Y 希望图的核心历经岁月侵蚀也保持不变,于是他想知道,有多大的概率,图 G 的最小外向生成树存在,且其边权和等于图 G 的最小生成树边权和。

你需要将答案对 (109+7) 取模。可以证明答案一定为有理数 ab,其中 ab 互质,且 b 不是 (109+7) 的倍数。因此你输出的数 x 需要满足 0x<109+7abx(mod109+7),可以证明这样的 x 唯一存在。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,T,分别表示测试点编号和测试数据组数,接下来输入每组测试数据。样例满足 c=0

对于每组测试数据,第一行两个整数 n,m,分别表示图 G 的点数和边数,接下来 m 行,第 i (1im) 行三个整数 ui,vi,wi,描述图 G 上的一条边。

输出格式

对于每组测试数据,输出一行一个整数,表示图 G 的最小外向生成树存在且其边权和等于图 G 的最小生成树边权和的概率,对 (109+7) 取模。

样例 1

input

0 2
2 1
1 2 1
3 3
1 2 2
1 3 2
2 3 2

output

750000006
171875002

explanation

该组样例共有 2 组测试数据。

  • 对于第一组测试数据,由于图上只有一条边,因此只要 G 上有边,G 的最小外向生成树边权和就一定等于 G 的最小生成树边权和。G 上存在边的概率为 34,故答案为 34,取模后的结果为 750000006
  • 对于第二组测试数据,在所有 22m=64G 中,有 13 种情况不满足 G 的最小外向生成树边权和等于 G 的最小生成树边权和:
    • G 为空图;
    • G 仅包含一条有向边,共 6 种情况;
    • G 仅包含两条有向边,且指向同一个节点,共 3 种情况;
    • G 仅包含两条有向边,且构成一个二元环,共 3 种情况。

由于所有情况等概率出现,因此答案为 11364=5164,取模后的结果为 171875002

【样例 2】

见选手目录下的 years/years2.inyears/years2.ans

该组样例共有 5 组测试数据。其中每组测试数据分别满足测试点 13467,891112,13 的限制。

【样例 3】

见选手目录下的 years/years3.inyears/years3.ans

该组样例共有 5 组测试数据。其中每组测试数据分别满足测试点 141617,1819,20212324,25 的限制。

子任务

对于所有测试点,

  • 1T5,
  • 2n15, n1mn(n1)2,
  • 1im, 1ui<vin, 1wim,
  • 1i<jm, (ui,vi)(uj,vj),即 G 没有重边,
  • 保证 G 连通。
测试点编号 n 特殊性质
13 6 A
46 15 B
7,8 9 C
911 12 C
12,13 14 C
1416 15 C
17,18 9
19,20 12
2123 14
24,25 15
  • 特殊性质 A:m6, 1im, wi2
  • 特殊性质 B:1i<jm, wiwj
  • 特殊性质 C:1im, wi=1