题解 CF917D 【Stranger Trees】

Soulist

2020-05-29 14:01:52

Solution

怎么别的做法都是 $\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)$ 的二项式反演就可以了。 核心代码: ```cpp 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 ; } } ``` 证明: - $\rm Matrix-Tree$ 定理。 我们先将 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}$ - $\rm prufer$ 序列。 将每个联通块视为一个大联通块,设其出现次数为 $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}$$