Luogu5296 [北京省选集训2019] 生成树计数

题意：给出一个带权无向完全图,求其所有生成树权值和的 次方之和。

，时限 。

---

统一省选 D2T3……

不难联想到矩阵树定理，但其只能求出所有生成树权值乘积的和。

考虑生成函数，不难想到用指数函数将乘法变为加法。

对于一条权值为 的边，构造生成函数权值 。

一棵生成树 的权值乘积为 。

提取 系数，是 ，这就得到答案了。

求多项式矩阵树即可，乘法和求逆可以 实现。

由于常数项均为 ，写法可略作简化。

复杂度 。