有一棵\(2m\)个点的有根树,其中有\(m\)个黑点, \(m\)个白点。
将黑点和白点分别指定顺序。
如果第\(i\)个黑点和第\(i\)个白点之间有祖孙关系,则记为好事件。(容易发现一共只有\(m\)个事件)
求好事件的个数恰好为\(0...m\)的(指定顺序的)方案数。\((m\le5000)\)
把恰好去掉，开始二项式反演
只认定\(k\)个好事件，其余随便
设\(f[u][k]\)为\(u\)子树中产生\(k\)个好事件(可能更多)的方案数\(v\in son[u]\)
\(f[u][k]=\sum\limits_{i=0}^nf[u][i]*f[v][k-i]\)
设\(s[u][0]\)为子树内白点个数，\(s[u][1]\)你懂
\(f[u][j+1]+=f[u][j]*(s[u][0]-j)\)
从剩余\(s[u][0]\)个白点找一个和根(黑点)匹配
\(F[k]\)为钦定\(k\)个好事件，其余放任自流的方案数，即\(f[1][0\sim m]\)
\(G[k]\)为恰好\(k\)个好事件方案数
\(F[k]=\sum\limits_{i=k}^n{i\choose k}G[i]\)
二项式反演
原文：https://www.cnblogs.com/shikeyu/p/13758985.html