P4002 [清华集训 2017] 生成树计数

在一个 $s$ 个点的图中，存在 $s-n$ 条边，使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 $a_i$ 个点。 现在我们需要再连接 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 $d_i$ 条边，那么这棵树 $T$ 的价值为： $$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$ 你的任务是求出所有可能的生成树的价值之和，对 $998244353$ 取模。

无

无

令 $i$ 表示大小为 $i$ 的原连通块，我们在连通块之间的连边有以下三种可能: - $2-3-4$ - $3-2-4$ - $2-4-3$ 价值和为: $$(2×3^2 ×4×2+3×2^2 ×4×2+2×4^2 ×3×2)×(1+2+1)=1728$$ --- 本题共有 $20$ 个测试点，每个测试点 $5$ 分。 - $20\%$ 的数据中，$n\le500$。 - 另外 $20\%$ 的数据中，$n \le 3000$。 - 另外 $10\%$ 的数据中，$n \le 10010, m = 1$。 - 另外 $10\%$的数据中，$n \le 10015,m = 2$。 - 另外 $20\%$ 的数据中，所有 $a_i$ 相等。 - $100\%$ 的数据中，$n \le 3\times 10^4,m \le 30$。 其中，每一个部分分的测试点均有一定梯度。