自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:56:56，当前版本为作者最后更新于2024-04-05 21:08:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先要注意到我们只要数树。进一步，删掉红色的点和相邻的边之后只剩下一片森林。

设 $x, y$ 计量白点 / 黑点，$W(x, y), B(x, y)$ 分别表示以白点 / 黑点为根的树的二元 EGF，可以列出方程

$$\begin{cases} W(x, y) = x \mathrm e^{B(x, y)} \\ B(x, y) = y \mathrm e^{W(x, y)} \end{cases} $$

对于 $\mathrm{type}=0$，我们只需计算

$$\left[\frac{x^ny^n}{n!n!}\right] \mathrm e^{W(x,y)+B(x,y)} $$

施多元 Lagrange 反演，可得其

$$\begin{aligned} &=\left[\frac{x^ny^n}{n!n!}\right] \mathrm e^{(n+1)(x+y)}(1-xy) \\ &=(n+1)^{2n}-n^2(n+1)^{2n-2} \\ &=(2n+1)(n+1)^{2n-2} \end{aligned} $$

对于 $\mathrm{type}=1$，我们需要计算

$$\left[\frac{x^ny^n}{n!n!}\right] \exp\left((x\partial_x+y\partial_y)(W+B)\right) $$

不妨在方程两侧取 $\partial_x$，可得

$$\begin{cases} \partial_x W = \mathrm e^{B} + W \partial_x B\\ \partial_x B = B \partial_x W \end{cases} $$

即

$$\begin{cases} x\partial_x W = \frac W{1-WB} \\ x\partial_x B = \frac{WB}{1-WB} \end{cases} $$

$\partial_y$ 的结果同理。因此我们需要计算

$$\left[\frac{x^ny^n}{n!n!}\right] \exp\left(\frac{W+B+2WB}{1-WB}\right) $$

施多元 Lagrange 反演知其

$$=\left[\frac{x^ny^n}{n!n!}\right] \exp\left(\frac{x+y+2xy}{1-xy}\right) \mathrm e^{n(x+y)}(1-xy) $$

换元，令 $x\mapsto st^{-1}, y\mapsto t$，可得其

$$\begin{aligned} &= n!^2 [s^n t^0]\exp\left(\frac{st^{-1}+t+2s}{1-s}\right) \mathrm e^{n(st^{-1}+t)}(1-s) \\ &= n!^2 [s^n t^0] \exp\left(\frac{(1+n(1-s))(st^{-1}+t)}{1-s}\right) \mathrm e^{\frac{2s}{1-s}} (1-s) \\ &= n!^2 [s^n] (1-s) \mathrm e^{\frac{2s}{1-s}} \sum_{j\ge 0} \frac1{j!^2} \left(\frac{1+n(1-s)}{1-s}\right)^{2j} s^j \\ &= n!^2 [s^n] (1-s) \mathrm e^{\frac{2s}{1-s}} {}_0F_1\left(;1;\frac{s(1+n(1-s))^2}{(1-s)^2}\right) \end{aligned} $$

是 D-Finite 的。时间复杂度 $O(n)$ 或 $O(\sqrt n \log n)$。