怎么别的做法都是 \mathcal{O(n^4)} 的神仙解法
先考虑设 g_i 表示至少有 i 条边重合的方案数，这等价于有 n-i 个联通块的方案数。那么对于 f_i 的计算就只需要二项式反演即可。
然后考虑如果我们已经知道了一个联通块划分 S 之后我们怎么做，可以证明假设当前有 k 个联通块，第 i 个联通块大小为 a_i，n=\sum a_i，则有生成树的数量为 \prod a\times n^{k-2}，证明的话放文章结尾，两种方式，可以挑选你喜欢的看（
于是对于一组划分，假设有 k 个联通块，则对于答案的贡献为 \prod a_i\times n^{k-2}，如果考虑 f_{i,j,k} 为 i 为根的子树划分了 j 个联通块，当前点所在的联通块大小为 k 的贡献和是可以轻易做到 \mathcal O(n^3) 的。
考虑 \prod a 的组合意义，我们可以视为将树划分为若干个联通块，每个联通块内放入一个球的方案数，这样通过树上背包的 trick 直接 dp 复杂度就是 \mathcal O(n^2) 了，然后 \mathcal O(n^2) 的二项式反演就可以了。
核心代码：
void dfs( int x, int fa ) {
dp[x][1][0] = 1, dp[x][1][1] = 1, sz[x] = 1 ;
for( int v : G[x] ) {
if( v == fa ) continue ; dfs( v, x ) ;
drep( j, 1, sz[x] ) drep( k, 1, sz[v] ) {
inc( bef[x][j + k][0], dp[x][j][0] * dp[v][k][1] % P ) ;
inc( bef[x][j + k][1], dp[x][j][1] * dp[v][k][1] % P ) ;
inc( bef[x][j + k - 1][0], dp[x][j][0] * dp[v][k][0] % P ) ;
inc( bef[x][j + k - 1][1], ( dp[x][j][1] * dp[v][k][0] + dp[x][j][0] * dp[v][k][1] ) % P ) ;
}
sz[x] += sz[v] ;
rep( j, 1, sz[x] ) dp[x][j][0] = bef[x][j][0], dp[x][j][1] = bef[x][j][1], bef[x][j][0] = 0, bef[x][j][1] = 0 ;
}
}
证明：
我们先将 S 中的所有联通块缩起来，考虑构建一张新图，我们连接 i\to j 的无向边，但是连接重边数量为 a_i\times a_j
那么根据矩阵树定理，我们可以得到其 Kirchhoff 矩阵为：
\begin{bmatrix}a_1(\sum a -a_{1})&...& 0\\0&a_2(\sum a-a_{2})&...0\\0&...&0\\0&...&a_k(\sum a-a_{k})\end{bmatrix}-\begin{bmatrix}0&...& a_{1}\times a_{k}\\a_{2}\times a_{1}&0&...a_{2}\times a_{k}\\a_{k-1}\times a_{1}&...&a_{k-1}\times a_{k}\\a_{k}\times a_{1}&...&0\end{bmatrix}
即：
\begin{bmatrix}a_1(n -a_{1})&...& ...&-a_1\times a_k\\-a_2\times a_1&a_2(n-a_{2})&...&a_2\times a_k\\...&...&...&...\\-a_{k-1}\times a_1&...&a_{k-1}\times(n-a_{k-1})&-a_{k-1}\times a_k\\-a_1\times a_{k}&...&...&a_k(n-a_{k})\end{bmatrix}
然后我们删除一行一列后的行列式即为答案：
\begin{bmatrix}a_1(n -a_{1})&...& ...\\-a_2\times a_1&a_2(n-a_{2})&...\\...&...&...\\-a_{k-1}\times a_1&...&a_{k-1}\times(n-a_{k-1})\end{bmatrix}
根据行列式的性质，我们把每行的一个公共系数 a_i 都提取出来后得到：
\prod_{i=1}^{n-1}a_i\begin{bmatrix}(n -a_{1})&...& ...\\-a_1&(n-a_{2})&...\\...&...&...\\-a_{1}&...&(n-a_{k-1})\end{bmatrix}
然后我们将第 2\to n-1 列都加到第 1 列上会得到：（这里的 n 指联通块数量）
\begin{bmatrix}a_k&...& ...\\a_k&(n-a_{2})&...\\...&...&...\\a_k&...&(n-a_{k-1})\end{bmatrix}
然后我们把每行都减去第一行得到：
\begin{bmatrix}a_k&...& ...\\0&n&...\\...&...&...\\0&...&n\end{bmatrix}
于是其行列式为 n^{k-2}a_k，所以答案为：\Big(\prod a_i \Big)n^{k-2}
将每个联通块视为一个大联通块，设其出现次数为 k，则其对于答案的贡献为 a_i^{k+1}
由于每个 \rm prufer 序列都是合法的，我们等价于求有 k-2 个位置，每个数出现次数为 i 时对于答案的贡献为 a_j^{i+1}，求所有方案的权值。
构建每个数的 EGF 为 F(a_i)，我们得到：
Ans=\prod a_i \bigg((k-2)![x^{k-2}]\prod F(a_i)\bigg)
Ans=\prod a_i\bigg((k-2)![x^{k-2}]\prod e^{a_ix}\bigg)
Ans=\prod a_i\frac{(k-2)!(\sum a_i)^{k-2}}{(k-2)!}
Ans=\prod a_i \times n^{k-2}