P4002 [Tsinghua Training 2017] Counting Spanning Trees

In a graph with $s$ vertices, there are $s-n$ edges, making the graph consist of $n$ connected components. The $i$-th connected component contains $a_i$ vertices. We now need to add $n-1$ edges to make the graph a tree. For a particular way of adding edges, let the $i$-th original connected component have $d_i$ edges going out. Then the value of this tree $T$ is: $$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right). $$ Your task is to compute the sum of the values of all possible spanning trees, modulo $998244353$.

The first line contains two integers $n, m$, as described above. The second line contains $n$ integers, where the $i$-th integer denotes $a_i$ $(1 \le a_i < 998244353)$. You can compute the total number of vertices $s$ from the $a_i$, so the value of $s$ is not given separately in the input.

Output a single line containing one integer, the answer.

Let $i$ denote an original connected component of size $i$. The edges added between components can be in the following three orders: - $2-3-4$ - $3-2-4$ - $2-4-3$ The sum of values is: $$ (2 \times 3^2 \times 4 \times 2 + 3 \times 2^2 \times 4 \times 2 + 2 \times 4^2 \times 3 \times 2) \times (1+2+1) = 1728. $$ --- This problem has $20$ test points, $5$ points each. - In $20\%$ of the testdata, $n \le 500$. - In another $20\%$ of the testdata, $n \le 3000$. - In another $10\%$ of the testdata, $n \le 10010, m = 1$. - In another $10\%$ of the testdata, $n \le 10015, m = 2$. - In another $20\%$ of the testdata, all $a_i$ are equal. - For $100\%$ of the testdata, $n \le 3\times 10^4, m \le 30$. Each group of test points for a partial score has a certain gradient. Translated by ChatGPT 5