题目大意

给定一个 $n$ 个点的原图（不一定是树）和一个 $n$ 个点的树形现图，求将现图的节点一一映射到原图的节点的方案数，使得现图中每条边在原图中对应节点之间也有边相连。

数据范围

$n \leq 17$，原图边数 $m \leq \frac{n(n-1)}{2}$

算法思路

1. 问题转化

我们要找的是双射 $p: V_T \to V_G$，使得对于现图的每条边 $(u,v)$，在原图中 $(p(u), p(v))$ 也是一条边。

这是一个树同构嵌入图的计数问题。

2. 核心 DP 状态设计

设： $f_{x, i, S}$ 表示将现图中以 $x$ 为根的子树映射到原图的节点集合 $S$，且 $x$ 映射到原图节点 $i$ 的方案数。

其中：

$x$：现图的节点

$i$：原图的节点

$S$：原图节点的子集，$|S| = \text{size}(x)$

3. 状态转移

对于 $x$ 的一个子节点 $y$，假设 $y$ 映射到原图节点 $j$，并且 $y$ 子树映射到原图节点集合 $T \subset S$，且 $i \notin T$，$|T| = \text{size}(y)$。

转移条件：

原图中 $i$ 与 $j$ 有边相连（因为 $(x, y)$ 是现图的边）。

$T$ 是 $S$ 的子集，且 $i \notin T$。

4. 实现细节

预处理每个节点数对应的所有子集 v2[k][s] 表示大小为 $k$ 的集合中大小为 $s$ 的子集。

预处理每个原图节点的邻居表 v3。

使用 to[] 数组快速取最低位的节点编号。

使用 nm[] 数组快速计算二进制中 1 的个数（即子集大小）。

5. 时间复杂度

状态数：$O(n \cdot n \cdot 2^n)$

转移时枚举子集：$O(3^n)$ 级别

总复杂度约 $O(n^2 \cdot 3^n)$，在 $n \leq 17$ 时可过。