神仙题……
考虑计算三个部分：1、\(n\)个点的森林的数量，这个是期望的分母；2、\(n\)个点的所有森林中存在最短路的点对的最短路径长度之和；3、\(n\)个点的所有路径中存在最短路的点对的个数之和，这个是用来计算需要取到\(m\)的点对的数量。
对于1，这个就直接对着树的数量的EGF做多项式exp即可。因为点之间有序所以用EGF，\(n\)个点的树的数量由Cayley定理就是\(n^{n-2}\)。
对于3，考虑枚举一个连通块大小，那么这种连通块大小的所有树的存在最短路的点对之和就是\(n^{n-2} \binom{n}{2}\)。然后我们需要求这个连通块在哪些森林中出现过，我们就需要拼一个森林进去，所以直接拿这个的EGF跟1中求出来的多项式做一个卷积就可以了。
对于2，发现那个平方不是很好搞，于是可以考虑平方的组合意义，实际上就是在\(i,j\)路径上的边上有序地任取两条边。我们可以考虑先枚举两条边，然后再考虑这两条边会在哪些路径上做出贡献。注意到两条不重合的边会把树分为三个连通块，而两条重合的边会分为两个连通块，那么我们可以再次交换求和顺序，先枚举两个/三个连通块，然后考虑如何在这两个/三个连通块之间连边、选择\(i,j\)。
考虑三个连通块的情况，两个连通块的情况类似。注意到如果三个连通块大小为\(a_1,a_2,a_3\)，边固定为1连向2、2连向3，\(i\)在1、\(j\)在3，那么连边的方式就有\(a_1a_2 \times a_2a_3\)种，选择起点的方式有\(a_1\)种，选择终点的方式有\(a_3\)种，那么总贡献就是\(a_1^2a_2^2a_3^2\)，只和连通块大小有关。不难再构造一个生成函数，每个位置表示大小为\(x\)的连通块的贡献，那么就只要考虑这个连通块会出现在哪些森林里，和3过程是一样的。
Gym102028G Shortest Paths on Random Forests 生成函数、多项式Exp
原文：https://www.cnblogs.com/Itst/p/11006311.html