题解 P7275 【计树】

对于一条边，如果它连接的两个端点的编号之差的绝对值不超过$1$，我们称这两个端点“连通”。 通过观察不难发现，最终我们得到的每个连通块都是一条长度不小于$2$的链，并且这条链上的点的编号是连续的一段区间。 接下来我们将构建整棵树看作一个这样的过程： 1. 将$1\sim n$分为$k$个区间，每段区间的长度不小于$2$。 2. 每段区间内部只有一种连边的方法，接着我们用$k-1$条边将这$k$个连通块连接起来。注意不能再有类似$(i,i+1)$这样的连边，我们称包含这种连边的情况为不合法情况。 比如当$n=4,k=2$时，有如下几种情况：  此时我们认为$\{1,2\}$是一个连通块，$\{3,4\}$是一个连通块，根据上面的定义，上面的四种情况中，前三种情况都是合法的，而最后一种情况不合法。 在计数的时候直接去除不合法的状态较为困难，因此可以考虑容斥。 记$f(i)$表示将$1\sim n$分为$i$个连通块（也就是区间），再连接$i-1$条边，可能出现不合法情况的方案数。 考虑如何计算$f$，假设我们已经将这$i$个区间分好了，第$i$个区间的大小为$a_i$。显然我们有$\sum a_i=n$，对于新加入的每条边来说，如果它的两个端点分别落在第$u$个区间以及第$v$个区间中，那么$u$这个端点有$a_u$种选法，$v$这个端点有$a_v$种选法。换言之，最终如果第$i$个连通块的度数为$j$，那么答案就要乘上$a_i^j$。 考虑对这棵树的`prufer`序计数。在`prufer`序中，一个点出现的次数为度数$-1$，而我们想要的贡献是$\prod a_i^j$。 因此我们可以将一个确定的$a_i$序列的贡献看作`prufer`序中所有出现$a_i$的乘积，再乘上每个连通块的度数的乘积。对于一个$a_i$来说，它在`prufer`序中出现了$j-1$次，再加上最后整体乘的一次，贡献恰好为$a_i^j$ 由于`prufer`序的长度为$i-2$，因此实际上这个$a_i$序列的贡献为 $$ \begin{aligned} \prod_{j=1}^ia_j\times (\sum_{k=1}^ia_k)^{i-2}=\prod a_i\times n^{i-2} \end{aligned} $$ 我们可以根据这个式子设计一个朴素的$dp$，将$n^{i-2}$拆为$n^i\times n^{-2}$。注意到$n^{-2}$与$a_i$是没有关系的，因此我们在$dp$的过程中可以只考虑$\prod a_i\times n^i$。 记$dp[i][j]$表示将$1\sim i$分为$j$段区间，一组分法的贡献为$\prod a_i\times n^i$时所有方案的和，它可以通过简单的转移求得。 接下来我们需要计算出每个区间的容斥系数，根据广义容斥原理，一组$a_i$的容斥系数为每个$a_i$的容斥系数的乘积。此时每种$a_i$序列的贡献乘上自己的容斥系数再求和就是答案。 我们希望在最终的方案中，长度小于$2$的区间对答案的贡献次数都为$0$，长度大于等于$2$的区间对答案的贡献次数都为$1$。 不妨设$A(x)$是容斥系数的生成函数，$x^i$项的系数就代表长度为$i$的区间对应的容斥系数。对于在最终的一段长度为$i$的区间来说，在我们计算$f$的过程中它有可能被分为若干段小区间，然后在这些小区间之间连上了若干条不合法的边。每种这样的划分都会导致$i$被统计了一次，因此此时每种区间在答案中的统计次数的生成函数为 $$ A(x)+A(x)^2+A(x)^3+\cdots=\frac{1}{1-A(x)}-1 $$ 我们希望长度小于$2$的区间被统计的次数都为$0$，因此 $$ \begin{aligned} \frac{1}{1-A(x)}-1&=x^2+x^3+x^4+\cdots\\ &=\frac{1}{1-x}-1-x \end{aligned} $$ 解得 $$ A(x)=\frac{x^2}{x^2-x+1} $$ 将$A(x)$展开，它的系数非常优美，为$\{0,1,1,0,-1,-1,0,1,1,0,-1,-1,\cdots\}$。 将$dp$写成生成函数的形式，由于$dp$的本质是将$n$划分为$i$段区间，我们有 $$ \begin{aligned} B(x)&=\sum_{j\geq 2}nx^jA_j\\ dp[n][i]&=B(x)^i[x^n]\\ ans&=\sum_i \frac{dp[n][i]}{n^2}\\ &=\sum_i\frac{B(x)^i[x^n]}{n^2}\\ &=\frac{\frac{1}{1-B(x)}[x^n]}{n^2} \end{aligned} $$ 调用一次多项式求逆即可。 [代码](https://paste.ubuntu.com/p/F62K6g4bQG/)