WC2019 数树

《从数树开始的数数生活》

求 $\sum\limits_{T_1}\sum\limits_{T_2} y^{n-|T_1 \cap T_2|}$ $T_1,T_2$ 是两个树的边集， $OP $ 为 $0,1,2$ 分别是给出两棵树，给出一颗树和不给出树

upd : 可能有 $y,y^{-1}$ 混用的问题，结合上下文大概能知道啥意思

OP = 0

开个 set 即可

OP = 1

我们先钦定选取了集合 $E$ 作为交集

”答案“为 $\sum\limits_{E} y^{n-|E|} F(E)$ $F(E)$ 为交集为 $E$ 的方案数，当然这个 $E$ 是至少的交集，还需要容斥

考虑如果我们选取了某些边，那么原树一定会被分割成几个连通块，我们需要求出这几个连通块连成一个树的方案数

假设分割成了 $m$ 个连通块，可知答案为$n^{m-2}\prod \rm{siz}_i$

把连通块看成一个点，从 purfer 序列的角度考虑，一个出现了 $d_i$ 次的点在原图中度数为 $d_i+1$

那么连通块之间可以连边，贡献就是 $\rm {siz}_i^{d_i+1}$

那么枚举 purfer 序列，就是 $\sum \limits_{\sum d_i=m-2}\dfrac{m!}{\prod\limits_{i=1}^{m} d_i!} \prod\mathrm{siz}_i^{d_i+1}$

$=m!\sum\limits_{\sum d_i = m-2} \prod\limits_{i=1}^{m}\dfrac{\mathrm {siz}_i^{d_i+1}}{d_i!}$

$=m!\prod\limits\_{i=1}^{m}\mathrm{siz}_i^{d_i}\sum\limits\_{\sum d_i =m-2}\prod \dfrac{\mathrm{siz}\_i^{d_i}}{d_i!}$

考虑 $\sum\limits_{\sum d_i =m-2}$ 这个条件，如果我们给后面的 $\prod$ 加一个占位的 $x^i$ 那么就是提取了 $m-2$ 项的系数

那么设 $G_k(x)=\sum \dfrac{\mathrm{siz}_{k}^i}{i!}x^i=e^{\mathrm{siz}_kx}$

那么 $\prod G_k(x) = \exp \{ \sum \mathrm{siz}_i \}=e^n$

那么原式为 $m!\prod \mathrm{siz}_i[x^{m-2}]e^n=n^{m-2}\prod \mathrm{siz}_i$

答案为 $\sum\limits\_{E} y^{n-|E|}F(E) = \sum\limits\_{E}y^{n-|E|}n^{n-|E|-2}\prod \mathrm{siz}_i=y^nn^{n-2}\sum\limits\_{E}{(yn)}^{-|E|}\prod \mathrm{siz}_i$

枚举边集和容斥都是指数级的，先解决枚举的问题

考虑比较麻烦的 $ \prod \mathrm{siz}_i $ ，可以组合意义理解为每个连通块选一个点的方案数，那么设 $dp_{x,0/1}$ 表示以 $x$ 为根的子树连通块，是否已经选点的方案数乘上贡献

那么枚举当前边在不在 $E$ 中然后 dp 即可做到线性

具体的有

当边 $(x,v)$ 在 $E$ 中时，有

$$dp_{x,0} \gets dp_{x,0} \times dp_{v,0} \times (yn)^{-1}$$

$$dp_{x,1} \gets (dp_{x,1} \times dp_{v,0}+dp_{x,0}\times dp_{v,1}) \times (yn)^{-1}$$

否则，有

$$dp_{x,0} \gets dp_{x,0} \times dp_{v,1}$$

$$dp_{x,1} \gets dp_{x,1}\times dp_{v,1}$$

$dp_{1,1}$ 即所求

然后是容斥的解决，考虑我们枚举的集合最终的真重合的边集 $S$ ，那么实际上它会被算 $\binom{|S|}{|E|}$ 次，那么因为我们枚举了所有的子集，所以他被算的答案就是 $\sum\limits_{i=0}^{|S|}\binom{|S|}{i}y^i=(y+1)^{|S|}$ 所以只要令 $y \to y-1$ 就可以得到正确的贡献

OP = 2

继续考虑一棵树的做法，设 $F(E)=n^{n-|E|-2}\prod \mathrm{siz}_i$ 即方案数

因为两个树都没有，所以只要枚举交集就可以生成出两个树 即 $\sum \limits_{E}y^{n-|E|}f(E)^2$ 同样是指数级的

当然也可以用 OP = 1 的做法把 $y$ 改写成 $y-1$ 来避免容斥，以下为了方便都写得 $y$

考虑枚举 $E$ 的大小，设 $g_i=\sum \limits_{|E|=i}f(E)^2$ 答案即为 $\sum\limits_i y^{n-i}g_i$

这样只要可以在合理的时间里算出来 $\{g_i\}$ 即可

因为siz太难打了 枚举每个连通块大小 $a_i$

显然 $g_m$ 有 $n-m$ 个连通块

先得让每个连通块连通，即连通块内部形成树 $\prod\limits_{i=1}^{n-m} a_i^{a_i-2}$

然后将每个点划分进连通块，一个多重集排列 $\prod\limits_{i=1}^{n-m} \dfrac{n!}{a_i!}$

然后我们枚举时赋予了顺序，但实际上连通块无序，所以除掉 $(n-m)!$

然后乘上 $f(E)^2$

以下的 $y$ 均为 $y^{-1}$ 因为 $y \to y-1$ 的方法是在 $y^{-1}$ 下才有正确贡献

$g_{m} = \sum\limits_{\sum a_i =n} \dfrac{n!}{(n-m)!}\prod\limits_{i=1}^{n-m} \dfrac{a_i^{a_i-2}}{a_i!}(n^{n-m-2}\prod \limits_{i=1}^{n-m}a_i)^2$

$\sum\limits_{m} y^{m} \sum\limits_{\sum a_i =n} \dfrac{n!}{(n-m)!}\prod\limits_{i=1}^{n-m} \dfrac{a_i^{a_i-2}}{a_i!}(n^{n-m-2}\prod \limits_{i=1}^{n-m}a_i)^2$

$n!\sum\limits_{m}y^{m}\dfrac{n^{2n-2m-4}}{(n-m)!}\sum\limits_{\sum a_i = n}\prod\limits_{i=1}^{n-m}\frac{a_i^{a_i}}{a_i!}$ (合并了 $\prod a_i^2 $ 和 $\prod a_i^{a_i-2}$)

下标代换 $m \gets n-m$

$n!n^{-4}y^n\sum \limits_{m=1}^{n}y^{-m} \dfrac{n^{2m}}{m!}\sum\limits_{\sum a_i = n}\prod \limits_{i=1}^{m}\dfrac{a_i^{a_i}}{a_i!}$

后面和 $OP=1$ 类似还是个卷积的 $[x^n]$

那么

$n!y^nn^{-4}\sum y^{-m}\dfrac{n^{2m}}{m!}[x^n]\left(\sum \dfrac{j^j}{j!}x^j \right)^m$

把前面的整合进去

$n!y^nn^{-4}[x^n]\sum \dfrac{\left( {n^2y^{-1} \sum \dfrac{j^j}{j!}x^j}\right)^m}{m!}$

后面的求和就是

$\exp \{n^2y^{-1}\sum \frac{i^i}{i!}x^i \}$

多项式 Exp 即可

最后还有一开始就提出去的 $y^n$

离谱