题解

思路

参观一个景点等价于从当前剩余图中删除一个度数不超过 $1$ 的顶点。因此题目要求统计“逐次删除当前叶子或孤立点”的有序前缀。

把所有当前度数不超过 $1$ 的点放入队列并不断剥离，最终留下的正是图的二核。二核中的点永远不能访问；所有可访问点组成若干棵树，其中一部分树通过根连接到二核，另一部分是整个连通分量都是树。

合并两个互不影响的部分时，若分别删除 $i,j$ 个点，则两个内部顺序可以用 $\binom{i+j}{i}$ 种方式交错。

做法

子任务 1：状态压缩

令 $dp[S]$ 表示已经访问集合 $S$ 的方案数。枚举尚未访问的顶点，若它在剩余图中的度数不超过 $1$，就转移到 $S\cup\{v\}$。按 $|S|$ 汇总即得各个答案。

子任务 2：森林树形 DP

先考虑一棵指定根且根的父亲永远未删除的树。令 $f_u[j]$ 表示在 $u$ 的子树中删除 $j$ 个点的方案数。先用组合数卷积合并所有儿子；要删除 $u$，必须先删完所有儿子，因此“删除整棵子树”的方案数等于“仅剩 $u$”的方案数。

无根树需要枚举最终作为根的顶点并把结果相加。删除 $j$ 个点后，若仍剩点，同一序列会被每个剩余点作为根计数一次，共 $s-j$ 次；若全部删除则只会由最后删除的顶点计数一次。因此除以 $\max(1,s-j)$。

子任务 3：二核与挂树

先做二核剥离。连接到二核的树以边界处可访问顶点为根，直接使用有根树 DP；完全脱离二核的树使用无根树处理。最后把所有树的多项式用带组合数的卷积合并。

模数 $10^9+9$ 是质数，除法通过快速幂求逆元完成。

复杂度

• 子任务 1：时间 $O(2^n n^2)$，空间 $O(2^n)$。
• 森林 DP 与满分算法：朴素重新选根实现为 $O(n^4)$ 时间、$O(n^2)$ 空间；二核剥离为 $O(n+m)$。