题解：P14454 [ICPC 2025 Xi'an R] Heart of Darkness

首先考虑算出不限制异色节点之间连边的方案数，再减去异色边小于 $k$ 的树的个数。
先考虑计算异色边数恰好为 $k$ 的情况，枚举黑点的数量 $i$，可以得到其为 $\sum_{i=1}^n \binom{n}{i}i^{i-2} (n-i)! [x^k y^{n-i}](\text e^{xT(y)})^i$

其中形式元 $x$ 计量异色边数，$y$ 计量白点数，$T(y)$ 是有标号有根树数量的 EGF。
那么异色边小于 $k$ 的树的个数就是 $S_k=n![y^n] \sum_{j=0}^{k-1} \frac{T(y)^j}{j!}\sum_{i=1}^\infty \frac{i^{i-2+j}}{i!}y^i$

由此也容易得到 $k \to \infty$ 时 $S_k$（即不限制异色边数的答案）为

然后使用另类 Lagrange 反演处理 $S_k$：

设 $a_m$ 为红色部分的 $[x^m]$ 项系数，则对于 $m\leq k$ 时，$a_m$ 显然是 $m^{m-2}/m!$，下面就只讨论 $m > k$ 的情况：

根据 Stirling 多项式的性质（P8561）可知，$a_m$ 是关于 $m$ 不超过 $2(k-1)$ 次的多项式，也就是说其 GF 是一个分母为 $(1-x)^{2k-1}$ 的有理分式。所以在计算出 $a_k$ 的前 $(2k-1)$ 项之后，就可以用一次卷积快速求出其 GF。

现在就有：

其中 $P(x)$ 是一个 $\Theta(k)$ 次多项式（可能比分母高 $2$ 次以内），此时可以直接以 $\Theta(n)$ 的时间复杂度计算 $S_k$。
具体地，简单求导可以得到 $\text e^{nx}/(1-x)^{2k-1}$ 系数的整式递推式，这样就容易处理了。

总时间复杂度 $\Theta(n+k^2)$。做到这个复杂度需要线性筛出 $f(i)=i^i$ 的函数值，但时间常数较大，朴素地使用快速幂也是可以通过的。

此题得到 $\Theta(n + k^2)$ 的复杂度做法后，总觉得不够优美，就试图找出更优的做法。可惜一直没有结果。

目前可以得到此问题的一些转化，如：

但这两个转化看起来都不是很有用... 该怎么办呢？