3422. [统一省选 2020]作业题

【题目描述】

  小 $W$ 刚刚在离散数学课学习了生成树的知识：一个无向图 $G = (V,E)$ 的生成树 $T$ 为边集 $E$ 的一个大小为 $|V| − 1$ 的子集，且保证 $T$ 的生成子图在 $G$ 中连通。

  小 $W$ 在做今天的作业时被这样一道题目难住了：

  给定一个 $n$ 个顶点 $m$ 条边（点和边都从 $1$ 开始编号）的无向图 $G$，保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$，对于一棵 $G$ 的生成树 $T$，定义 $T$ 的价值为：$T$ 所包含的边的边权的最大公约数乘以边权之和，即：

$val(T)=(\sum_{i=1}^{n-1}w_{e_i})\times \gcd(w_{e_1},w_{e_2},\cdots,w_{e_{n-1}})$

  其中 $e_1,e_2,\cdots,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输入】

3 3
1 2 4
2 3 6
1 3 12

【样例1输出】

192

【样例1解释】

$G$ 共有三棵生成树：

$T_1 = \{(1,2),(2,3)\}$，价值为 $10 × 2 = 20$。

$T_2 = \{(1,2),(1,3)\}$，价值为 $16 × 4 = 64$。

$T_3 = \{(1,3),(2,3)\}$，价值为 $18 × 6 = 108$。

总和为 $192$。

【样例2】

点击下载样例2

【数据规模与约定】

对于 $10\%$ 的数据满足：$m ≤ 15$。

另有 $20\%$ 的数据满足：$m ≤ n$。

另有 $20\%$ 的数据满足：$w_i$ 均相同。

另有 $20\%$ 的数据满足：$w_i$ 均为质数。

对于 $100\%$ 的数据满足：$1 ≤ n ≤ 30，1 ≤ m ≤ \frac{n(n-1)}{2}，1 ≤ w_i ≤ 152501$。

【来源】

HAOI2020 Day1 Task3