对于生成虚tree进行DP——CF1097G Vladislav and a Great Legend
首先
考虑如何 \(dp\) \(\sum_X{F(X)\choose i}\)。
设 \(f_{x,i}\) 表示考虑 \(x\) 的子树中的若干种点集选择方案，其中选择了 \(i\) 条边的方案数，这里这里并不要求 \(x\) 本身在不在虚树中。
-
一个考虑是对于每一种虚树，我们在深度最浅处记录答案。
-
另一个考虑是，为了方便转移，我们要时刻认为其祖先上有点被选择。
为了方便转移，设 \(g_{x,i}\) 表示在 \(f_{x,i}\) 的基础上考虑上 \(x\) 到 \(fa\) 的边。即 \(g_{x,i}=f_{x,i}+f_{x,i-1}\)，考虑到若 \(x\) 的子树中的选择方案是空集，则一定不能选择这条边，所以 \(g_{x,1}\gets g_{x,1}-1\)。
初始时 \(f_{x,0}=2\) 表示 \(x\) 可以选或不选。
现在考虑合并一个 \(y\)，显然 \(f'_{x,i+j}\gets f_{x,i}g_{y,j}\)
但由于这样可能有 \(x\) 不再虚树中的情况，所以 \(as_i\gets as_i+f_{x,i}-\sum_{y}g_{y,i}\)。即减去仅有一个子树的情况，因为这样 \(f_{x,0}\) 应该等于 \(1\) 才对。
最后答案就是 \(\sum_{i=1}^k{k \brace i}i!as_i\)。
背包合并时，限制枚举到 \(\min(k,siz[x])\)，即：
lop(i,0,min(k,siz[x]))lop(j,0,min(k,siz[y]))(tmp[i+j]+=f[y][j]*f[x][i])%=MOD;
可以将复杂度减为 \(\mathcal O(nk)\)。
证明考虑，转移相当于选择 \(x\) 中dfn后 \(k\) 大的，\(y\) 中前 \(k\) 小的进行匹配
那么每个点相当于仅和其前 \(2k\) 与其后 $2k $ 个点匹配一次，所以复杂度为 \(\mathcal O(nk)\)。