在一张 $n$ 个点的完全图中，每条边的权值是 $1\sim m$ 中的一个整数，求最小生成树权值的期望。

先考虑 $m=2$ 的情况，此时相当于每条边有 $\frac12$ 的概率存在，求联通块的个数。

先把概率问题转化为计数问题，然后除以样本空间大小。

考虑更简单的情况，每条边有 $\frac12$ 的概率存在，求只有一个联通块的方案数。

我们对图中的点 $1$ 进行讨论。钦定 $1$ 所在的联通块大小为 $i$，在剩余 $n-1$ 个点中选 $i-1$ 个，钦定联通块内的 $i$ 个点与外面没有连边，外面乱连，那么方案数

\[f_k=2^{\binom n2}-\sum_{i=1}^{n-1}f_i\binom{n-1}{i-1}2^{\binom{n-i}2}\]

那联通块总个数怎么求？我们去枚举 $n$ 个点的一个 $k$ 元子集，去计算这个子集对答案的贡献。当且仅当一个 $k$ 元子集与其他 $n-k$ 个元素没有任何连边时，这个 $k$ 元子集才有贡献，因此

\[\mathbb E[\text联通块个数]=\frac1{2^{\binom{n}2}}\left(\sum_{k=1}^n\binom nkf_k2^{\binom{n-k}2}\right)\]

当然要除以样本空间大小，把贡献转成期望。 上述这个式子，我们尽管不知道联通块个数的具体分布列，但是我们通过拆贡献把期望求出来了。

现在回到原题，对于一个边权 $j\in[1,m]$，我们对其 01 分组。具体地说，我把小于等于 $j$ 的边都看成 $0$，大于 $j$ 的边权都看成 $1$，那么此时每条边联通的概率就是 $\frac{m-j+1}n$，把上述式子做适当调整，把原概率 $p=\frac12$ 改成 $p=\frac{m-j+1}m$ 即可，这个式子的结果记为 $g(p)$。

这样我们发现一条边权为 $j$ 的边在所有小于等于 $j$ 时 01 分组都贡献了一次。我们给它在每次被计算到时加起来就行，这样答案就是

\[\sum_{j=1}^mg\left(\frac{m-j+1}m\right)\]

注意到 $g(p)$ 是关于 $n$，次数为 $\mathcal O(n^2)$ 的多项式。

我们令 $h_j=g(\frac{m-j+1}m)$，那么我们就要求 $h$ 的前缀和 $h_1+h_2+\cdots+h_m$。

只需将 $\mathcal O(n^2)$ 个点值带入 $g$ 后对其求前缀和，然后在插值，变回多项式，最后回带即可。