P1 旅行商问题
统计哈密顿路径的数量。
对于长度为 $n$ 的路径，如果所有的点都在路径中出现过，那么这条路径就是合法的。
枚举未经过的点的集合（可能是空集），计算此时长度为 $n$ 的路径的数量，然后容斥一下就能得到答案。
时间复杂度 $O(2^n \cdot n^2)$ 。
P2 UOJ185 小星星
考虑将树上的点映射到图上的某个点。如果图上的每个点都被映射到了，那么这种方案就是合法的。
如果不限制“每个点都被映射到”，这个东西就是个经典的树形 dp。
容斥枚举没有被映射到的点集，然后做树形 dp 即可。
时间复杂度 $O(2^n \cdot n^3)$。
P3 k染色问题
题意：给定一个包含 $n$ 个结点的图和 $k$，判断它是否可以 $k$ 染色。$n\le 22$
考虑选取 $k$ 个独立集，如果每个点都被至少一个独立集包含，那么这种染色方案就是合法的。注意如果存在点被多个独立集包含，我们仍然认为方案是合法的，因为我们只关心合法染色方案的存在性（而不是个数）。
枚举没有被独立集包含的点，然后计算从没有包含它们的独立集中选出 $k$ 个的方案数。容斥一下就能得到答案。
不包含某个特定点集的独立集数可以高维前缀和求出。
时间复杂度 $O(2^n\cdot n)$