菜王的 blog

唉，终究还是无法战胜。

首先看到这个 $2^{cyc}$ 就非常的神秘啊，考虑赋予他一个组合意义。我最开始想的是环长为奇数的时候尝试构造一个 $2$ 的系数，否则构造出一个 $0$ 的系数，但是这个太难编了，根本编不出来。那么我们考虑另一种思路：再另外乘上一个选环方案，每个环都可以选或不选。

设 $o$ 表示奇环的个数，$e$ 表示偶环的个数，那么我们将 $2^{cyc}$ 改写成 $2^o[e = 0]$ 就能干掉第二个限制。那么 $[e = 0] = \sum_{i = 0}^e \binom ei (-1)^i$，所以我们就可以改编上述思路：再另外乘上一个选环方案，每个环都可以选或不选，奇环系数为 $1$，偶环系数为 $-1$，那么就只剩下第三个限制了。

考虑交换求和顺序，先钦定节点集合 $S$ 内部组成若干个环，那么剩下的节点的系数就好算了，显然是 $(n - 1)^{n - |S|}$。

考虑 $S$ 内部的贡献。若没有 ban 边这个限制，那么 $|S| = 1$ 时答案显然为 $1$，否则都为 $0$。这可以由一个双射导出：考虑将一个置换环拆开，或将两个置换环合并，都会使得偶环个数的奇偶性改变。具体构造双射考虑 $1, 2$ 是否在同一置换环中即可。

若有 ban 边这个限制，考虑继续对 ban 边进行容斥，即强制钦定 ban 的边被选并乘上 $-1$。那么这么钦定之后合法情况一定是一堆链。显然奇链和前面的单点等价，所以我们考虑偶链。考虑在 $c$ 条链，目前答案为 $tot$ 的情况下插入一条偶链的影响，要么自己新开一个环并乘上 $-1$，否则不变。注意后者有 $c$ 种方案。那么 $tot$ 实际上相当于乘上 $(c - 1)$。先插入所有奇链再插入偶链，那么若奇链条数 $> 1$ 时答案本来就是 $0$，插入偶链并不会带来任何影响。若奇链条数 $= 1$ 时插入偶链会使答案乘 $0$。若没有奇链且偶链长度 $> 1$ 也是同理。所以只有钦定到恰好组成一条链的情况答案不是 $0$。若链是偶链，那么钦定的边数是奇数，会乘两次 $-1$，恰好抵消掉了。所以我们得出结论：若 $S$ 在树上组成了一条链，那么 $|S|$ 内部的贡献为 $1$，否则为 $0$。

那么我们直接统计即可做到 $O(n)$。真搞不懂这种题怎么出出来的。

code