A5914. 「联合省选 2020 A」作业题
编程题
省选/NOI-
知识点
题目描述
小 W 刚刚在离散数学课学习了生成树的知识：一个无向图 $G = (V,E)$ 的生成树 $T$ 为边集 $E$ 的一个大小为 $|V|-1$ 的子集，且保证 $T$ 的生成子图在 $G$ 中连通。
小 W 在做今天的作业时被这样一道题目难住了：
给定一个 $n$ 个顶点 $m$ 条边（点和边都从 $1$ 开始编号）的无向图 $G$，保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$，对于一棵 $G$ 的生成树 $T$，定义 $T$ 的价值为：$T$ 所包含的边的边权的最大公约数乘以边权之和，即：
$$ val(T) = \left(\sum_{i=1}^{n-1} w_{e_i}\right) \times \gcd (w_{e_1}, w_{e_2}, \dots, w_{e_{n-1}}) $$
其中 $e_1, e_2, \dots, e_{n-1}$ 为 $T$ 包含的边的编号。
小 W 需要求出 $G$ 的所有生成树 $T$ 的价值之和，他做了很久也没做出来，请你帮帮他。由于答案可能很大，你只需要给出答案对 $998244353$ 取模后的结果。
小 W 在做今天的作业时被这样一道题目难住了：
给定一个 $n$ 个顶点 $m$ 条边（点和边都从 $1$ 开始编号）的无向图 $G$，保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$，对于一棵 $G$ 的生成树 $T$，定义 $T$ 的价值为：$T$ 所包含的边的边权的最大公约数乘以边权之和，即：
$$ val(T) = \left(\sum_{i=1}^{n-1} w_{e_i}\right) \times \gcd (w_{e_1}, w_{e_2}, \dots, w_{e_{n-1}}) $$
其中 $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$。
接下来 $m$ 行，每行三个正整数 $u_i, v_i, w_i$，第 $i$ 行表示一条无向边连接 $u_i$ 号点和 $v_i$ 号点，权值为 $w_i$。
输出格式
仅一行一个整数，表示答案对 $998244353$ 取模后的结果。
输入输出样例
输入 #1
3 3 1 2 4 2 3 6 1 3 12
输出 #1
192
说明/提示
$10\%$ 的数据满足：$m\le 15$。
另有 $20\%$ 的数据满足：$m \le n$。
另有 $20\%$ 的数据满足：$w_i$ 均相同。
另有 $20\%$ 的数据满足：$w_i$ 均为质数。
$100\%$ 的数据满足：$2\le n\le 30, 1\le m \le \frac {n(n-1)}2, 1\le w_i \le 152501$。
另有 $20\%$ 的数据满足：$m \le n$。
另有 $20\%$ 的数据满足：$w_i$ 均相同。
另有 $20\%$ 的数据满足：$w_i$ 均为质数。
$100\%$ 的数据满足：$2\le n\le 30, 1\le m \le \frac {n(n-1)}2, 1\le w_i \le 152501$。