CF917D Stranger Trees 笔记

这里有一样东西，要求树上选 $k$ 个连通块，连通块大小的乘积。

于是可以向组合意义转换：每个连通块任选一个点，求方案数，于是设 $f_{i,j,0/1}$ 表示以 $i$ 为根，选出 $j$ 个连通块，当前连通块是否选择，时的方案数。

这里还有一个树上背包优化空间，不知道出题人卡这个干什么。

由于以 $u$ 为根的背包大小 $<{\mathrm{sz}}_u$，因此让 $f_{u,i}\to f_{{\mathrm{dfn}}_u+i}$ 即可，空间优化到 $O(n)$。