CodeForces 512D Fox And Travelling

pufanyi

发布于：Feb 14, 2020

有一张 $n$ 个点 $m$ 条边的简单无向图，每次选择一个度数小于等于 $1$ 的点然后将其删除，对于每个 $k$ 求删去 $k$ 个点的方案数。 $n\le 100,\,m\le \frac{n\times(n-1)}{2}$ 。

首先环上点肯定删不掉，如果一个连通块之间有两个环，那么被两个环夹着的点肯定也删不掉。

接下来我们考虑两件事情，一件事情就是如果一个连通块本身不是一棵树，那么如果它的一部分点能被删掉，那这部分点肯定组成一个森林，每棵树肯定之靠着一个环。外面的点先被删，而环旁边的点是最后被删的，那我们相当于对于每棵树就可以以环旁边那个点为根，然后 dp 上去。这个 dp 很方便，考虑到没两个点只会在其 LCA 上被合并一次，所以这部分的复杂度是 $\mathcal{O}(n^2)$ 的。

然后我们考虑这个连通块本身就是一棵树的情况，这个情况下其实就是每个点都是可以作为 dp 的根的，这样做出来的话如果全删完那显然是对的，但是发现如果不删完的话是会算重的。我们考虑不删完的一种方案，如果留了 $x$ 个节点，那么对于留下来的这 $x$ 个节点，每个节点作为根 dp 的时候都会把这种方案算一遍。于是其实就是这种方案对答案的贡献是 $x$ 而不是 $1$ 了。于是我们就可以直接把 dp 出来的结构除以 $x$ 便使答案了。