题解 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}

调用一次多项式求逆即可。

代码