题解：AT_agc070_b [AGC070B] Odd Namori

· · 题解

非常人类智慧的一道题，感觉这辈子都想不到一点/ll。

有什么用呢？我们发现此时对于任意的图 $G$ 来说，$\sum f(S)=[G\text{ 中不存在偶环}]$，这是因为当 $S$ 里面存在偶环的时候，我们可以去掉其中的一个偶环，则两个点集的偶环个数奇偶性正好相反且贡献抵消，更严谨地说明是考虑到有 $[even=0]=\sum_{i=0}^{even}\binom{even}{i}(-1)^i$，所以这么转化是正确的。 现在我们成功去掉了偶环的限制，只需要对所有 $G$ 的 $\sum f(S)$ 求和即可。考虑交换求和顺序，枚举一个点集 $S$，计算所有 $G$ 对 $S$ 的贡献是什么。 首先对于 $S$ 外的点的连边方案是容易算的，只需要保证每个点不连向它在树上的父亲即可，当 $1\in S$ 时方案数是 $(n-1)^{n-|S|}$，否则是 $n\times (n-1)^{n-|S|-1}$，现在要解决的是 $S$ 内在满足没有树边限制时的方案。 先退一步想，如果 $S$ 内不需要满足非树边的限制贡献应该是啥。事实上我们有，当且仅当 $|S|=1$ 的时候会有 $1$ 的贡献，否则可以通过构造双射的方式把 $S$ 的贡献消成 $0$。具体来说，考虑 $S$ 中编号最小的两个点，交换它们的出边，生成的环就会产生分裂或者合并，此时类比置换环可知偶环个数的奇偶性一定会改变，所以贡献抵消。 不妨继续对非树边的限制进行容斥，钦定 $S$ 内必须连若干条树边（假设钦定了 $e$ 条边），并分配上 $(-1)^e$ 的容斥系数。容易发现，我们钦定的树边必须在树上构成若干条祖先后代的链，否则会存在入度大于 $1$ 的点使得无法构成环。进一步地，发现这些链可以缩成一些单点，按照链上点数的奇偶性将缩完之后的点分为奇点和偶点。我们注意到，缩点后的问题和上面不要求非树边限制的情况是很像的，如果缩点后有超过 $1$ 个点可以使用同样的方式构造双射把贡献消掉，所以只有缩点后是单点，也就是钦定了树上一条祖先后代链的时候才可能有贡献（还可以发现，这时候 $S$ 必须正好是这条链上的点）。 那如果缩点后是一个单点贡献应该是什么呢？如果剩下的点是奇点，此时我们钦定了偶数条边所以容斥系数是 $1$，形成了一个奇环所以 $f(S)=1$，相乘得到贡献是 $1$；如果剩下的点是偶点，此时我们钦定了奇数条边所以容斥系数是 $-1$，形成了一个偶环所以 $f(S)=-1$，相乘得到贡献是 $1$。 现在终于得到了最终的结论：当且仅当 $S$ 是树上的一条祖先后代链的时候才会对答案产生贡献，此时给答案累加上 $S$ 外的点连边方案数即可。因此我们只需要知道树上每个长度的祖先后代链有几条就可以直接算答案了，这是容易的，当然可能要判下 $1$ 号点在链里的情况，可以做到 $O(n)$。 这题的每一步构造都太巧合了啊，怎么回事哦？？