给定 $m$ 种颜色和 $n$ 个点，第 $i$ 种颜色有 $c_i$ 个点，求将其连接成树且极大同色连通块大小 $\le k$ 的方案数。

先让我们回顾 $k=1$ 的情况。对每种颜色容斥，考虑先钦定构建出若干同色连通块，再进行容斥。
根据经典 Prufer 结论，我们需要计算的是对每种颜色钦定出的连通块的贡献积。
那么一种 $c$ 个点的颜色的贡献无非就是 $$ \left[\frac{z^c}{c!}\right] \exp \left(-nT(-z)\right) = (-1)^c \left[\frac{z^{c-1}}{(c-1)!}\right] (\mathrm e^{-nz})' \cdot \mathrm e^{cz} = n(n-c)^{c-1} $$

其中 $T(z) = z\mathrm e^{T(z)}$ 是有标号有根树。

考虑一般的情况。不难想到我们还是需要确定一个容斥系数。
考虑这种容斥系数需要满足什么？令其为 $P(z)$，具体地，其刻画了我们容斥时的基本单位构建为连通块的方案数。
在上例中，无非就是 $-T(-z)$。

再具体一点，如果我们直接用 $P(z)$ 作为连通块刻画一棵树，那么结果就应该恰好是所有不超过 $k$ 个结点的有根树。

其在代数上的刻画有两种方式，一种是直接应用和上面类似的方法，也就是对于所有 $n$ 要满足 $$ n^{-2} \left[\frac{z^n}{n!}\right] \exp nP(z) = [n\le k] n^{n-2} $$

（来自 jiangly）

但是这并不方便进行代数计算。那我们不妨直接利用复合方程。那我们无非就是考虑根所占的连通块被 $P(z)$ 刻画，即 $$ F(z) = P\left(z \mathrm e^{F(z)}\right) $$

那我们让 $\left[\frac{z^n}{n!}\right] F(z) = [n\le k] n^{n-1}$，就可以得到 $P(z)$。具体地，可以设 $Q(z) = z\mathrm e^{F(z)}$，那么 $$ P(z) = F(Q^{\langle -1 \rangle}(z)) $$

那么问题就变成了多项式复合逆和复合。

考虑到最后每个颜色的贡献应该是 $$ \left[\frac{z^c}{c!}\right] \exp nP(z) = \left[\frac{z^{c-1}}{(c-1)!}\right] (\exp nF(z))' \left(\frac{z}{Q(z)}\right)^c = \left[\frac{z^{c-1}}{(c-1)!}\right] nF'(z) \exp((n-c)F(z)) $$

可以 $\Theta(n \log n)$ 解决。

（来自 EI）