对于确定的边集 \(E_1,E_2\)，显然方案数等于 \(y^{n-|E_1\cap E_2|}\)（因为如果一条边都出现那么两个端点取值相同）。
Subtask 0
两棵树都给定，只需要开一个 set<pair<int,int>> 然后数一下重边数目快速幂输出一下就可以了。
Subtask 1
首先，为了方便，我们取 \(y\) 的逆元，以后说的 \(y\) 均为取逆元之后的，然后我们只需要只计算 \(\sum y^{|E_1\cap E_2|}\) 的值，以下认为我们求的 \(ans\) 均为取完逆元后 \(\sum y^{|E_1\cap E_2|}\) 的值 ，然后把求出的结果再乘上 \(y^n\)（这里的 \(y\) 是最初输入的）就可以了。
我们考虑枚举 \(E=E_1\cap E_2\)，然后再计算包含边集 \(E\) 的方案数。为了计算这个，我们需要先考虑子问题：现在给定 \(m\) 个连通块，第 \(i\) 个连通块的大小为 \(siz_i\)，求把它们联通成一棵树的方案数。
我们考虑 prufer 序列。首先，一个 prufer 序列对应一棵无根树；另外，对于树中的任意一点 \(i\)，若其在 prufer 序列中出现了 \(d_i\) 次，则 \(x\) 的度数为 \(d_i+1\)。这样的话，我们枚举每个连通块在 prufer 序列中出现了几次，式子如下： \[ (m-2)!\sum\limits_{d_1+d_2+\dots+d_{m}=m-2}\prod_{i=1}^{m}\frac{siz_i^{d_i+1}}{d_i!} \] 这个式子的意思是枚举每个数的出现次数，然后每一条出边都可以连连通块内的任何一个点，方案数为 \(siz_i\)，有 \(d_i+1\) 条出边总方案数为 \(siz_i^{d_i+1}\)。然后因为是一个排列，所以要做一个多重集排列。
为了上下统一，我们提出一个 \(\prod\limits_{i=1}^msiz_i\)，那么就变成了 \[ (m-2)!\left(\prod\limits_{i=1}^msiz_i\right)\sum\limits_{d_1+d_2+\dots+d_{m}=m-2}\prod_{i=1}^{m}\frac{siz_i^{d_i}}{d_i!} \] 我们注意到 \(\frac{siz_i^{d_i}}{d_i!}\)，这等于 \([x^{d_i}]e^{siz_ix}\)，又看到乘积与 \(\sum d_i=m-2\) ，这提示我们写成 EGF 相乘，那么就可以化成 \[ \begin{aligned} &(m-2)!\left(\prod\limits_{i=1}^msiz_i\right)[x^{m-2}]\prod\limits_{i=1}^me^{siz_ix}\\ =&(m-2)!\left(\prod\limits_{i=1}^msiz_i\right)[x^{m-2}]e^{\sum\limits_{i=1}^msiz_ix}\\ =&(m-2)!\left(\prod\limits_{i=1}^msiz_i\right)[x^{m-2}]e^{nx}\\ =&(m-2)!\left(\prod\limits_{i=1}^msiz_i\right)\frac{n^{m-2}}{(m-2)!}\\ =&n^{m-2}\prod\limits_{i=1}^msiz_i \end{aligned} \]
（注：这个式子也可以通过其它方法得到）发现这个式子竟然惊人的简洁，我们尝试来计算答案。如果你直接枚举重合的边集，然后计算方案数再乘上权值，你不难得到这个式子： \[ ans=\sum\limits_{E\subseteq E_1}y^{|E|}n^{n-|E|-2}\prod\limits_{i=1}^{n-|E|}siz_i \] 如果你直接写一个枚举边集的指数暴力，你会发现你 WA 的很惨，是哪里出了问题呢？我们发现我们现在是钦定了一些重边然后剩下的随便连，但是如果你随便连的边又和 \(T_1\) 里的边重复了，那权值就不是 \(y^{|E|}\) 了。
怎么办？其实解决方法很简单（这里指式子的变化很少而不是很好想到 /kk）：我们注意到，对于某种方案，假设我们钦定的边集大小为 \(|E|\)，实际上重合的边集为 \(E'\)，那么实际上 \(E'\) 的权值一共被算了 \(\binom{|E'|}{|E|}\) 次。也就是说一种方案，实际被算的贡献为 \(\sum\limits_{i=0}^{|E'|}\binom{|E'|}{i}y^i\)，不难发现这是一个二项式定理的形式，它等于 \((y+1)^{|E'|}\)。那么如果我们让 \(y\) 减去 \(1\)，算的就是正确的了。
所以我们直接 y--，就可以继续用上面那个式子了。（注意从现在开始包括下一个子任务我们所说的 \(y\) 都是取完逆元再减 \(1\) 之后的）
到目前为止，算法依旧是指数级的，我们考虑用树形 dp 来计算边集的贡献。
首先，为了方便后续计算，我们提一个 \(n^{n-2}\) 出来。
有一个比较好想的朴素方法：设 \(f[i][j]\) 表示以 \(i\) 为根的子树，目前以 \(i\) 为根的连通块大小为 \(j\) 的所有贡献。那么转移枚举当前点和某个儿子之间的边选不选：如果选加上对应的连通块大小，并且因为多选了一条边乘上 \(yn^{-1}\)，如果不选就把儿子的连通块大小乘进去。
这样做是 \(O(n^2)\) 的，无法通过。我们考虑一个等价关系：选若干个连通块，再把每个联通块的 \(siz\) 相乘，这等价于选若干个连通块，并且在每个连通块内选出一个代表点的方案数。所以我们可以优化状态：设 \(f[i][0/1]\) 为以 \(i\) 为根的子树，\(i\) 所在的连通块内是否选了代表点的方案数乘上对应的权值。这样的话转移我们枚举边连不连，代表点选不选，具体方程如下： \[ \begin{aligned} &f[i][0]=yn^{-1}f[i][0]f[to][0]+f[i][0]f[to][1]\\ &f[i][1]=yn^{-1}(f[i][0]f[to][1]+f[i][1]f[to][0])+f[i][1]f[to][1] \end{aligned} \] 注意一下等号右边的 \(f[i][x]\) 指的是算这个儿子之前的。这样 \(f[1][1]\) 乘上我们之前说的就是答案。
Subtask 2
为了方便，我们设 \(f(E)=n^{m-2}\prod\limits_{i=1}^msiz_i,m=n-|E|\)，即确定了 \(E\) 中的边剩下连成一棵树的方案数。那么答案即为 \[
\sum\limits_Ef^2(E)y^{|E|}
\] 即钦定重边的边集，并且计算贡献，上一个子任务的关于 \(y\) 的容斥在这里依旧是适用的，因为我们之前 y-- 过了所以这里没有 \(-1\)。
我们枚举连通块的个数，设 \(g(i)=\sum\limits_{|E|=i}f^2(E)\)，则 \(ans=\sum\limits_{i=0}^{n-1}g(i)y^i\)。我们尝试计算 \(g(i)\)，这可以通过枚举每个连通块的大小来实现，下面先给出式子： \[ g(s)=\sum\limits_{a_1+a_2+\dots+a_{n-s}=n}\frac{n!}{(n-s)!}\prod_{i=1}^{n-s}\frac{a_i^{a_i-2}}{a_i!}\left(n^{n-s-2}\prod\limits_{j=1}^{n-s}a_j\right)^2 \] 这个式子的意义是，首先枚举集合大小，然后计算所有满足连通块大小等于所枚举的森林的方案数：这等于先划分集合，这是一个多重集划分，方案数为 \(\frac{n!}{\prod\limits_{i=1}^{n-s}a_i!}\)。然后因为集合是无序的，所以需要再除掉 \((n-s)!\)，即集合的全排列数，最后括号里的内容即为 \(f^2(E)\)。我们把括号展开，然后尝试化简 \[ \begin{aligned} g(s)&=\sum\limits_{a_1+a_2+\dots+a_{n-s}=n}\frac{n!}{(n-s)!}\prod_{i=1}^{n-s}\frac{a_i^{a_i-2}}{a_i!}n^{2n-2s-4}\prod\limits_{j=1}^{n-s}a_j^2\\ &=n^{2n-2s-4}\frac{n!}{(n-s)!}\sum\limits_{a_1+a_2+\dots+a_{n-s}=n}\prod_{i=1}^{n-s}\frac{a_i^{a_i}}{a_i!}\\ \end{aligned} \] 然后枚举答案 \[ \begin{aligned} ans&=\sum_{s=0}^{n-1}y^sn^{2n-2s-4}n!\sum\limits_{a_1+a_2+\dots+a_{n-s}=n}\frac{1}{(n-s)!}\prod_{i=1}^{n-s}\frac{a_i^{a_i}}{a_i!}\\ &=n!\sum_{s=0}^{n-1}y^sn^{2n-2s-4}\frac{1}{(n-s)!}\sum\limits_{a_1+a_2+\dots+a_{n-s}=n}\prod_{i=1}^{n-s}\frac{a_i^{a_i}}{a_i!}\\ \end{aligned} \] 然后我们用 \(n-s\) 替换 \(s\) \[ \begin{aligned} ans&=n!\sum_{s=1}^{n}y^{n-s}n^{2s-4}\frac{1}{s!}\sum\limits_{a_1+a_2+\dots+a_s=n}\prod_{i=1}^s\frac{a_i^{a_i}}{a_i!}\\ &=\frac{n!y^n}{n^4}\sum_{s=1}^{n}y^{-s}n^{2s}\frac{1}{s!}\sum\limits_{a_1+a_2+\dots+a_s=n}\prod_{i=1}^s\frac{a_i^{a_i}}{a_i!}\\ \end{aligned} \] 和我们上面推出生成树计数的式子一样，后面的求和+连乘积也可以写成 EGF 的形式，即 \[ \begin{aligned} ans&=\frac{n!y^n}{n^4}\sum_{s=1}^{n}y^{-s}n^{2s}\frac{1}{s!}[x^n]\left( \sum\limits_ {i=1}^{\infty}\frac{(ix)^i}{i!}\right)^s \end{aligned} \] 然后我们把枚举的 \(s\) 也丢进去 \[ \begin{aligned} ans&=\frac{n!y^n}{n^4}[x^n]\sum\limits_{s=1}^n\frac{\left(\frac{n^2}{y}\sum\limits_{i=1}^{\infty}\frac{i^i}{i!}x^i\right)^s}{s!}\\ &=\frac{n!y^n}{n^4}[x^n]e^{\left(\frac{n^2}{y}\sum\limits_{i=1}^{\infty}\frac{i^i}{i!}x^i\right)} \end{aligned} \] 需要一个多项式 exp，这样这道题就做完了。
其实最后一部分也可以先写出树贡献的 EGF 然后根据 exp 的组合意义直接得到森林的 EGF。
最后还有一点，对于子任务1,2，因为我们 y-- 过，所以当输入的 \(y=1\) 的时候会出现奇怪的问题，我们需要特判一下。
题解可能和 @Zhang_RQ 的比较像，因为他是我们学长，这题是他讲的，借鉴了一部分他的博客。
代码如下：
1 |
|