题解 U145111 【无谓感伤】

· · 个人记录

来证明一下结论. 考虑容斥，限制相当于同色的边不能选. 那么我们首先选好同色的边，然后把所有连通块连起来. 根据 prufer 序列的经典结论，连起来的方案数是

n^{m-2}\prod_{i=1}^m size_i

提出 n^{-2} 再乘上容斥系数，那么每个连通块会造成 (-1)^{size-1}\cdot n\cdot size 的贡献. 显然不同颜色的点之间是独立的，我们只需要计算出一种颜色的贡献然后全乘起来.

一棵有标号有根树的 EGF 是

T(z)=\sum_{i\geq 1}\frac{i^{i-1}}{i!}z^i

它满足 T(z)=ze^{T(z)}，也就是 T^{-1}(z)=ze^{-z}. 而现在我们的一个连通块的贡献 EGF 为

\sum_{i\geq 1}\frac{i^{i-2}}{i!}n\cdot i(-1)^{i-1}z^i=-nT(-z)

于是一个具有 c 个点的颜色的答案为

[z^c]e^{-nT(-z)}=(-1)^c\cdot \frac{1}{c}[z^{c-1}](e^{-nz})'\left(\frac{z}{T^{-1}(z)}\right)^c=n(n-c)^{c-1}

于是最终的答案就是

n^{m-2}\prod_{i=1}^m(n-c_i)^{c_i-1}