题解 P5206 【[WC2019] 数树】

· · 题解

Solution

问题 1

连通块数等于点数减边数，所以这个东西相当于是 y ^{n - |T _1 \cap T _2|}，简单统计一下重合了几条边就行。

问题 2

第一想法肯定是二项式反演咯。设 f _i 表示钦定了 i 条边在两棵树中同时出现，第二棵树的方案数；而 g _i 表示恰好有 i 条边同时出现的方案数。则有：

g _i = \sum _{j = i} ^{n - 1} (-1) ^{j - i} {j \choose i} f _j

我的第一思路是算出 f _{0, \cdots, n - 1}，然后反演出 g 再算答案。

思考一下 f _i 怎么算。写成式子，大概是枚举一个大小为 i 的边集，然后将这个边集里面的边连起来之后，会得到 n - i 个连通块。而由 Prufer 序列的有关知识可以知道，将这些连通块任意连成树的方案数是 n ^{n - i - 2} \prod _{j = 1} ^{n - i} a _j，其中 a _j 表示第 j 个连通块的大小。

这个东西其实非常不好算，因为限定了边集合的大小，最好可能也只能做到 O(n ^2) 的 DP（没有细想）。自己推到这里的时侯就迷茫了。

但是实际上可以回到原来的位置先展开一下式子，可能就没有必要求出每个 i 的 f _i 值了。

答案可以表示成如下的形式（第一行），接着推下式子：

\begin{aligned} & \sum _{i = 0} ^{n - 1} g _i y ^{n - i} \\ =& y ^n \sum _{i = 0} ^{n - 1} y ^{- i} \sum _{j = i} ^{n - 1} (-1) ^{j - i} {j \choose i} f _j \\ =& y ^n \sum _{j = 0} ^{n - 1} (-1) ^j f _j \sum _{i = 0} ^j (-1) ^i {j \choose i} y ^{-i} \\ =& y ^n \sum _{j = 0} ^{n - 1} f _j (\frac {1 - y} y) ^j \\ \end{aligned}

最后一步是二项式定理合并，然后把 (-1) ^j 乘进去。

为了公式书写的简洁美观一点，下面写的 f _j 是表示钦定了有 n - j 条边（也就是 j 个连通块）时，剩下的边任选，连成一棵树的方案数。

然后式子会变成第一行的样子。展开 f _j 一下：

\begin{aligned} & \sum _{j = 1} ^{n} f _j (1-y) ^{n - j} y ^j \\ =& \sum _{j = 1} ^n (1-y) ^{n - j} y ^j \sum _{\{a\}, |a| = j} n ^{j - 2} \left ( \prod _{i = 1} ^j a _i \right) \\ =& \frac {(1-y) ^n} {n ^2} \sum _{\{a\}, |a| = j} \prod _{i = 1} ^j \frac {yn}{1 - y} a _i \\ \end{aligned}

然后仔细观察一下后面那一块怎么求。

相当于是，将树化成若干个连通块，每个连通块的贡献是一个常数 \frac {yn} {1 - y} 乘上其连通块大小，一个方案的贡献是所有连通块贡献的乘积，求所有方案的贡献和。

一个比较垃圾的 DP 是设 f(u, i) 表示 u 子树内 u 所在连通块大小为 i 的贡献和。然后 O(n ^2) DP 就行。

考虑其组合意义，相当于是从一个连通块中选 1 个点出来，产生 \frac {yn} {1 - y} 的贡献。那么设 f(u, 0/1) 表示 u 子树内，u 所在的连通块是否已经选了一个点的贡献和，简单 O(n) DP 即可。

问题 3

还是沿用问题 2 的思路，无非也就是前面多了一个枚举 T _1 的求和号而已。

会得到这么一个东西：

\frac {(1-y) ^n} {n ^2} \sum _{\{a\}, |a| = j} \left( \prod _{i = 1} ^j \frac {yn}{1 - y} a _i \right) \sum _{\{a\} \in T _1} 1

然后后面那个求和号也可以利用前面的那个结论，也就是

\frac {(1-y) ^n} {n ^4} \sum _{\{a\}, |a| = j} \left( \prod _{i = 1} ^j \frac {yn^2} {1 - y} a _i ^2 \right )

后面这一块……其实挺明显的。它的实际意义是若干个连通块组合在一起，然后贡献是每个连通块贡献的乘积，并且连通块大小的和是 n。这很像生成函数吧。

由于带标号，所以采用 EGF。那么设

F(x) = \sum _{k \ge 0} \frac {y n ^2} {1 - y} k^2 \frac {x ^k} {k!}

然后我后来才发现这上面这玩意是错的。虽然一个连通块的贡献是这个式子，但是你还要考虑到连出一个连通块的方案数，应该是 k ^{k - 2}。所以真正的函数应该是这样：

F(x) = \sum _{k \ge 0} \frac {y n ^2} {1 - y} k^k \frac {x ^k} {k!}

森林由若干个连通块无序组合而成，所以最终答案是 \frac {(1-y) ^n} {n^4} n! [x ^n] \exp(F(x))。写个 \exp 就 O(n \log n) 了。

我的题解是不是比其他人都短啊

Code

代码咕了

补上了。由于太长了去剪贴板里面看吧