中文
日本語
English
| P7043「联合省选 2020 A卷」作业题 | ||
|
问题描述
A卷Day2T3
小 W 刚刚在离散数学课学习了生成树的知识：一个无向图 \(G = (V,E)\) 的生成树 \(T\) 为边集 \(E\) 的一个大小为 \(|V|-1\) 的子集，且保证 \(T\) 的生成子图在 \(G\) 中连通。
小 W 在做今天的作业时被这样一道题目难住了：
给定一个 \(n\) 个顶点 \(m\) 条边（点和边都从 $1$ 开始编号）的无向图 \(G\)，保证图中无重边和无自环。每一条边有一个正整数边权 \(w_i\)，对于一棵 \(G\) 的生成树 \(T\)，定义 \(T\) 的价值为：\(T\) 所包含的边的边权的最大公约数乘以边权之和，即：
其中 \(e_1, e_2, \dots, e_{n-1}\) 为 \(T\) 包含的边的编号。
小 W 需要求出 \(G\) 的所有生成树 \(T\) 的价值之和，他做了很久也没做出来，请你帮帮他。由于答案可能很大，你只需要给出答案对 $998244353$ 取模后的结果。
输入格式
第一行两个正整数 \(n,m\)，表示 \(G\) 的点数和边数。
接下来 \(m\) 行，每行三个正整数 \(u_i, v_i, w_i\)，第 \(i\) 行表示一条无向边连接 \(u_i\) 号点和 \(v_i\) 号点，权值为 \(w_i\)。
输出格式
仅一行一个整数，表示答案对 $998244353$ 取模后的结果。
提示
样例 1
样例输入 1
3 3
1 2 4
2 3 6
1 3 12
样例输出 1
192
样例解释 1
\(G\) 共有三棵生成树：
\(T_1 = \{(1, 2), (2, 3)\}\)，价值为 $10\times 2 = 20$。
\(T_2 = \{(1, 2), (1, 3)\}\)，价值为 $16\times 4 = 64$。
\(T_3 = \{(1, 3), (2, 3)\}\)，价值为 $18\times 6 = 108$。
总和为 $192$。
样例 2
点击查看
样例输入 2
4 6
1 2 113400
2 3 131040
1 3 126000
2 4 90720
3 4 95760
1 4 131040
样例输出 2
684150634
数据范围与提示
$10\%$ 的数据满足：\(m\le 15\)。
另有 $20\%$ 的数据满足：\(m \le n\)。
另有 $20\%$ 的数据满足：\(w_i\) 均相同。
另有 $20\%$ 的数据满足：\(w_i\) 均为质数。
$100\%$ 的数据满足：$1\le n\le 30, 1\le m \le \frac {n(n-1)}2, 1\le w_i \le 152501$。