题解：AT_arc121_e [ARC121E] Directed Tree

很 edu 的题目。

看到这个东西人类应该不可能想不到容斥。

考虑二项式反演。

二项式反演要注意钦定，恰好。

我们设

g_i

表示钦定要选

i

个条件条件的方案数。

这里只是借鉴了二项式反演的谓词，其他实际上没有关系。

\mathcal{f_n}=\sum_{i=0}^n (-1)^{i} g_i

考虑怎么求出

g_i

。

考虑 dp，设

dp_{i,j}

表示以

i

为根，钦定

j

这个条件合法的方案数。

dp_{i,k+j} =dp_{i,k+j} + dp_{i,k} \times dp_{v,j} \\ dp_{i,j} =dp_{i,j} + dp_{i,j-1} \times (sz_i-j)

然后

g_i=f_{1,i} \times (n-i) !

，因为你剩下的是随便选。

复杂度是

O(n^2)

，就是树上背包。

文章操作