[WC2019] 数树

题目大意

题目的模型是有两棵$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$。

写个暴力,然后发现这玩意并不对,我们冷静分析一下,发现我们钦定出来的边集只是两个边集的交的一个子集,而不是最终的交。

那么接下来有两种处理方法,容斥和组合恒等式,这里只介绍组合恒等式的处理方法。

我们发现,我们设最终的交集为$|S|$,若我们钦定的集合的大小为$k$,那么这种大小的连通块对$S$的贡献就是.${|S| \choose k} \times val$。

我们知道有组合恒等式$y^{k} = \sum \limits _ {i=0} ^{k} {k \choose i} (y-1) ^ i$。

那么如果我们将权值$val$设置为$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)$

代码