题解 P5206 【[WC2019] 数树】

推荐去[这里](https://zhang-rq.github.io/2019/04/09/WC2019-%E6%95%B0%E6%A0%91/)看 # 题目大意 题目的模型是有两棵$n$个点树，求$y^{|T _ 1 \cap T _ 2 |}$。（$T _ 1,T _ 2$分别是两棵树的边集。） 有三个部分，分别是： - 给定两棵树求答案。 - 给定一棵树，然后求另一棵树是$n^{n-2}$种情况时的答案和。 - 只给一个$n$，求出两棵树在所有情况下的答案和（共$(n^{n-2})^2$种情况） # 题解 我们一次考虑每个部分的做法。 ## 给定两棵树 这部分只有普及组难度，随便用个$set$记一下就行了。 ## 给定一棵树 我们不妨钦定一些$T _ 1$中的边为必选边，那么考虑$T _ 2$的方案数是多少（记为$F$）。 我们发现，加入一些必选边后，$T _ 2$被连成了若干连通块，我们假设形成了$m$个连通块（说明钦定了$n-m$条边）。 有一个很直观的想法就是这$m$个连通块的生成树个树（即$m^{m-2}$），但是显然算少了很多，因为两个连通块间的边的个数不是$1$，而是两个连通块大小的乘积。 那么我们不妨从$m^{m-2}$的本质来考虑这件事，众所周知，$m^{m-2}$的来源是$prufer$序列，那我们从$prufer$序列来审视这个问题。 我们发现，假设一个连通块的出现次数在$prufer$的出现次数为$d _ i$，它的大小为$siz _ i$，显然，它的度数为$d _ i+1$，它对答案有一个$siz _ i^{d _ i+1}$的乘法贡献。 我们现在不妨枚举每个连通块在$prufer$序列的出现次数并且枚举$prufer$序列，注意要处理多重集合的排列。 那么方案数很容易写出：  我们随手化简一下，可以得到  我们接下来来考虑后面这一坨东西的组合意义，相当于我们先给每个连通块分配了一些位置，然后每个位置可以填$siz _ i$种数字。那么我们可以直接考虑每个位置能填的数字，显然种类数就是$\sum _ {i} siz _ i =n$，那么可以进一步化简得到最终形式。  也就是说，我们现在可以暴力枚举边集，然后计算答案  接下来，为方便起见，我们令$y=y^{-1}$，最后统一乘$y^n$。 写个暴力，然后发现这玩意并不对，我们冷静分析一下，发现我们钦定出来的边集只是两个边集的交的一个子集，而不是最终的交。 那么接下来有两种处理方法，容斥和组合恒等式，这里只介绍组合恒等式的处理方法。 我们发现，若我们钦定的集合为$E$，那么它对两棵树边集交的集合$S$的贡献次数是$|S| \choose |E|$。 我们知道有组合恒等式$y^{k} = \sum \limits _ {i=0} ^{k} {k \choose i} (y-1) ^ i$。 那么如果我们将权值设置为$y-1$，再进行刚才的做法，发现每个集合的贡献恰好是$y^k$。 于是我们得到了一个指数级的做法，枚举边集。我们接下来考虑将复杂度降到$poly(n)$。 一个很自然的想法就是用树形$dp$来优化上述过程，我们发现，一个点状态只和这个点所在的连通块大小有关。那么可以设$f _ {x,s}$为考虑完以$x$为根的子树后，$x$所在的连通块的大小为$s$。这样，我们在合并儿子时考虑下$x$到儿子的这条边选不选，并且乘上相应的系数（$1$或$y^{-1}n^{-1}$）进行转移即可，使用$siz$优化，复杂度为$\mathcal{O}(n^2)$。 这个做法的复杂度我们显然无法接受，考虑继续优化。 我们发现，$\prod{siz _ i}$的组合意义是从每个连通块分别选出一个点的方案数。那么我们可以这个组合意义设置新的$dp$状态。 我们设$f _ {x,0/1}$为考虑完$x$为根的子树，$x$所在连通块是否已经选点了的方案数，转移讨论一下就行了，注意每个点必须要选出一个点。复杂度$\mathcal{O}(n)$。 ## 给定零棵树 这里我们继续沿用给定一棵树时的做法。 我们设$f(E)=\prod _ {i=1} ^{m} siz _ i \times n^{m-2}$，其中，$E$是一个边集，$m$表示将$E$中的边连接后形成的连通块个数，$\{siz\}$是每个连通块的大小。 那么我们枚举一个边集$E$，且这个边集必须是某棵树的边集的子集，那么这个边集对答案的贡献是$f(E)^2 y^{|E|}$。 所以答案就是$\sum \limits _ {E} y^{|E|} f(E)^2 $。 我们不妨枚举$|E|$，我们设$g _ i=\sum \limits _ {|E|=i} f(E)$，答案可以进一步化简为$\sum \limits _ {i=0}^{n-1} y^i g _ i$。 那么我们接下来就要处理$\{g\}$数组了。 由$f(E)$的计算式，我们不妨考虑枚举将$E$中的边连起来后每个连通块的大小$\{a\}$，然后可以得到以下式子：  解释下这个式子是怎么来的： 首先，我们需要让这些连通块内部都是连通的，就是$\prod \limits _ {i=1}^{n-s} a _ i^{a _ i-2}$，然后，我们将$n$个点划分到这些集合中，就是多重集合的排列，体现在式子中就是$n! \prod \limits _ {i=1}^{n-s} \frac{1}{a _ 1!}$，最后，这些连通块其实是无序的，但是我们在枚举大小的时候是作为有序的做的，所以我们要除掉$(n-s)!$，最后那个平方项就是$f(E)^2$。 然后我们将这个式子带到答案的式子中，并进行一番化简：  注意，在第四个式子中，我用将$s$替换为了$n-s$。 然后我们发现第二个求和号的那个限制很难搞，但观察一下可以发现其实是个$\bf EGF$的形式，我们用$\bf EGF$来替换第二个求和号部分，并继续化简：  然后写个多项式$\bf Exp$就做完了。 复杂度：$\mathcal{O}(n \log n)$ [代码](https://github.com/Zhang-RQ/OI_Code/blob/master/LOJ/2983.cpp)