题解：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)，就是树上背包。