CF1097G Vladislav and a Great Legend 题解

$f(S)^k$ 看上去不太好维护，考虑经典套路斯特林反演：

于是题目给出的式子可以化为：

问题在于对每个 $i$ 快速计算 $\displaystyle\sum\limits_{S\subseteq\lbrace1,2,3,\ldots,n\rbrace}\binom{f(S)}i$ 的值。

考虑这个东西的组合意义，容易发现对每个 $i$，其答案可以看作是在 $S$ 集合内点组成的虚树的点集上选 $i$ 条边的方案数。

设 $f_{i,j}$ 表示当前处理了 $i$ 为根的子树内有 $j$ 条虚树的边的方案数，转移类似于树上背包合并，时间复杂度为 $O(nk)$。统计答案的时候套路的在深度最低的结点上统计即可。实现起来细节比较多。