TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7043
  • 题目
  • P7043「联合省选 2020 A卷」作业题
    限制 : 时间限制 : - MS   空间限制 : 524288 KB
    评测说明 : 3s,512MB
    问题描述

    A卷Day2T3

    小 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$ 取模后的结果。

    输入格式

    第一行两个正整数 \(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$。