P6624 [NOI Qualifier Joint Exam 2020 Paper A] Homework Problem

Little W has just learned about spanning trees in a discrete mathematics class: a spanning tree $T$ of an undirected graph $G=(V,E)$ is a subset of the edge set $E$ with size $|V|-1$, and the subgraph generated by $T$ is connected in $G$. While doing today’s homework, Little W got stuck on the following problem: Given an undirected graph $G$ with $n$ vertices and $m$ edges (both vertices and edges are numbered starting from $1$), it is guaranteed that there are no multiple edges and no self-loops in the graph. Each edge has a positive integer weight $w_i$. For a spanning tree $T$ of $G$, define the value of $T$ as: the greatest common divisor of the weights of the edges in $T$ multiplied by the sum of these weights, that is: $$ val(T)=\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}}) $$ where $e_1,e_2,\dots,e_{n-1}$ are the indices of the edges included in $T$. Little W needs to find the sum of the values of all spanning trees $T$ of $G$. Since the answer may be very large, you only need to output it modulo $998244353$.

The first line contains two positive integers $n,m$, representing the number of vertices and edges of $G$. The next $m$ lines each contain three positive integers $u_i,v_i,w_i$. The $i$-th line describes an undirected edge connecting vertex $u_i$ and vertex $v_i$, with weight $w_i$.

Output a single integer in one line, representing the answer modulo $998244353$.

[Sample Explanation 1] There are three spanning trees in $G$: $T_1=\{(1,2),(2,3)\}$, with value $10\times 2=20$. $T_2=\{(1,2),(1,3)\}$, with value $16\times 4=64$. $T_3=\{(1,3),(2,3)\}$, with value $18\times 6=108$. The total sum is $192$. [Constraints] $10\%$ of the testdata satisfies: $m\leq 15$. Another $20\%$ of the testdata satisfies: $m \leq n$. Another $20\%$ of the testdata satisfies: all $w_i$ are equal. Another $20\%$ of the testdata satisfies: all $w_i$ are prime numbers. $100\%$ of the testdata satisfies: $1\leq n\leq 30, 1\leq m \leq \frac {n(n-1)}{2}, 1\leq w_i \leq 152501$。 Translated by ChatGPT 5