题意简述
给定一张 $n$ 个点 $m$ 条边的简单无向图，每次可以选择一个度数为 $1$ 的点删除，求删去 $0, 1, \dots, n$ 个点的方案数模 $10^9 + 9$。两种方案不同当且仅当二者在某一步选择的点不同。$1\le n\le 100$ 。
主要思路
在环上的点一定无法被选择，因此去除所有删不掉的点后图是一个森林。对每棵树分别计算选择 $0$ 到 $size$ 个点的答案，卷积起来即可。注意如果一个点在原图中与不可选的点之间有连边，那么它在这个连通块里一定是最后被选择的。注意以这个点为根时，在一个点的子树里的点都被选后，其自身才能被选。考虑树形 dp ，令 $f_{i, j}$ 表示在 $i$ 子树里选出 $j$ 个点的方案，转移为对子树的 $f$ 卷积。
现在考虑一个连通块在原图中即为树的情况。我们无法确定选择所有点时最后被选的点。这种情况对所有点都以其为根做一次 dp ，对于有 $i$ 个点选了的方案，会在不以这 $i$ 个点为根时都计算一次，所以对于没有选完而选了 $i$ 个点的方案，除以 $size - i$ 即可去重。
单次树上背包时间复杂度 $O(n^2)$ ，所以总时间复杂度 $O(n^3)$ 。
参考代码
咕