题目大意

题目的模型是有两棵$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$序列，注意要处理多重集合的排列。

那么方案数很容易写出：

$F= m! \sum _ {\sum _ {i=1}^{m} d _ i=m-2} \prod _ {i=1}^{m} \frac{siz _ i^{d _ i+1}}{d _ i!}$

我们随手化简一下，可以得到

$F= \prod _ {i=1}^{m} siz _ i \times m! \sum _ {\sum _ {i=1}^{m} d _ i=m-2} \prod _ {i=1}^{m} \frac{siz _ i^{d _ i}}{d _ i!}$

我们接下来来考虑后面这一坨东西的组合意义，相当于我们先给每个连通块分配了一些位置，然后每个位置可以填$siz i$种数字。那么我们可以直接考虑每个位置能填的数字，显然种类数就是$\sum {i} siz _ i =n$，那么可以进一步化简得到最终形式。

$F = \prod _ {i=1} ^{m} siz _ i \times n^{m-2}$

也就是说，我们现在可以暴力枚举边集，然后计算答案

$Ans = \sum _ {E \subset T _ 1} y^{n-|E|} n^{n-|E|-2} \prod _ {i=1} ^{n-|E|-2} siz _ i\\ Ans = y^n n^{n-2} \sum _ {E \subset T _ 1} y^{-|E|} n^{-|E|} \prod _ {i=1} ^{n-|E|-2} siz _ i$

接下来，为方便起见，我们令$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}$，然后可以得到以下式子：

$g _ s = \sum _ {\sum _ {i=1}^{n-s}a _ i=n}\frac{n!}{(n-s)!} \prod _ {i=1}^{n-s} { \frac{a _ i^{a _ i-2}}{a _ i!}} ( \prod _ {i=1} ^{n-s} a _ i \times n^{n-s-2} )^2$

解释下这个式子是怎么来的：

首先，我们需要让这些连通块内部都是连通的，就是$\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$。

然后我们将这个式子带到答案的式子中，并进行一番化简：

$\begin{aligned} Ans &= \sum _ {s=0}^{n-1} \sum _ {\sum _ {i=1}^{n-s}a _ i=n}\frac{n!}{(n-s)!} \prod _ {i=1}^{n-s} { \frac{a _ i^{a _ i-2}}{a _ i!}} ( \prod _ {i=1} ^{n-s} a _ i \times n^{n-s-2} )^2 \\ Ans &= \sum _ {s=0}^{n-1} n!\frac{n^{2 * (n-2-s)}}{(n-s)!} \sum _ {\sum _ {i=1}^{n-s} a _ i = n} \prod _ {i=1}^{n-s} {\frac{a _ i^{a _ i}}{a _ i!}}\\ Ans &= n! \sum _ {s=0}^{n-1} y^s \frac{n^{2 * (n-2-s)}}{(n-s)!} \sum _ {\sum _ {i=1}^{n-s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \\ Ans &= n! \sum _ {s=1}^{n} y^{(n-s)} \frac{n^{2 * (s-2)}}{s!} \sum _ {\sum _ {i=1}^{s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \\ Ans &= \frac{n!y^n}{n^4} \sum _ {s=1}^{n} y^{-s} \frac{n^{2 * s}}{s!} \sum _ {\sum _ {i=1}^{s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \end{aligned}$

注意，在第四个式子中，我用将$s$替换为了$n-s$。

然后我们发现第二个求和号的那个限制很难搞，但观察一下可以发现其实是个$\bf EGF$的形式，我们用$\bf EGF$来替换第二个求和号部分，并继续化简：

$\begin{aligned} Ans &= \frac{n!y^n}{n^4} \sum _ {s=1}^{n} y^{-s} \frac{n^{2*s}}{s!} [x^n] \left( {\sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right) ^ s\\ Ans &= \frac{n!y^n}{n^4} [x^n] \sum _ {s=1}^{n} \frac{\left( {\frac{n^2}{y} \sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right) ^ s}{s!}\\ Ans &= \frac{n!y^n}{n^4} [x^n] e^{\left( {\frac{n^2}{y} \sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right)} \end{aligned}$

然后写个多项式$\bf Exp$就做完了。

复杂度：$\mathcal{O}(n \log n)$

代码