二项式反演

定义 fif_i 表示有将 ii 个不同的元素组成的特定结构的方案数,gig_i 表示从 ii 个元素任意选出一些(可以不选)组成特定结构的方案数。

对于知道 fif_i 或者 gig_i 中的任意一个就可求解另外一个,其公式如下:

gn=i=0n(ni)fig_n=\sum\limits_{i=0}^n{n\choose i}f_i

fn=i=0n(ni)(1)nigif_{n}=\sum\limits_{i=0}^n{n\choose i}(-1)^{n-i}g_i

就是容斥,直接感性理解就完了。

思路

题目求的是 gig_i,考虑把 fif_i 用 DP 算出来。

定义 fx,if'_{x,i} 表示节点 xx 为根的子树内有,拟定有 ii 个满足父子关系的,那么只考虑子树内的情况有:

fx,i+jfx,i+j+pson(i)fp,k×fx,jf'_{x,i+j}\gets f'_{x,i+j}+\sum\limits_{p\in \text{son}(i)} f'_{p,k}\times f'_{x,j}

最后把 xx 的贡献加进去,设 ss 是颜色与 xx 不同的子树内的节点数量,那么就有:

fx,ifx,i+fx,i1×max(s(j1),0)f'_{x,i}\gets f'_{x,i}+f'_{x,i-1}\times \max(s-(j-1),0)

考虑剩余的随便选,也就是 fi=f1,i×(n2k)!f_i=f'_{1,i}\times (\dfrac{n}{2}-k)!

最后把 ff 丢给二项式反演就算出了 gig_i 也就是答案了,时间复杂度为 O(n2)O(n^2)