Libre OJ 题目地址

题意简述

给定一张 $n$ 个点 $m$ 条边的无向图和它的一个生成树。出于某种原因,点的编号在生成树中被打乱了。现在重新给生成树中每个节点编号,求合法方案树。

编号方案合法当且仅当,一对在生成树上有相连的边的点,无向图中对应的点对间也存在一条边。

输入 $n,m$ ,编号混乱的生成树和原来的无向图。输出合法的编号方案数。

本题中,$n \leq 17$。

思路

我们可以定义状态 $dp_{(i,j,S)}$ 表示当生成树中点 $i$ 的新编号为 $j$,子树内已有编号为 $S$ 时,所有的合法方案数。这样暴力转移的时间复杂度为 $\Theta(n^3\times 3^n)$,显然是不够优秀的。

我们需要降低复杂度,直接去掉 $dp$ 数组的第三维。这样不可避免地出现了编号重复的问题,我们需要将不合法的方案从答案中删掉。

那么我们可以利用容斥。枚举最后的编号方案用掉的编号集合 $S$,对包含在 $S$ 中的点进行 $dp$。令确定的 $S$ 的方案数为 $f$,最后的答案就是

$$\sum_{ |S|=n }f-\sum_{ |S|=n-1 }f+\sum_{ |S|=n-2 }f – \cdots$$

总时间复杂度为 $\Theta(n^3 \times 2^n)$。

代码