P17781 千早爱音不是罪过 题解

来复读一下第一篇题解。

直接枚举所有排列显然你是不可行的，因此考虑枚举哪些边紧密相连。钦定若干条边相邻是简单的，因此考虑子集反演，给每条边染成黑 / 白 / 灰三种颜色，其中黑边要求强制相邻并保留在最终的连通块中，白边要求强制相邻且不保留到最终连通块中（贡献为 $-1$），灰边不做额外的限制。考虑这个为什么是对的。固定一个排列，设真正相邻的树边集合为 $E$，则若最终选定的黑边集合 $B\subseteq E$ 则其余实际相邻的边可以染白色也可以染灰色，这些选择的容斥系数恰好当且仅当黑边恰好为真正相邻的边时才会留下贡献，因此只需要枚举黑白灰三种边并计算其带容斥系数后的贡献即可。

然后容易发现每个点最多向子树内连一条非灰的边。因此所有染色边一定是形成了若干条从上到下的链。套路的把每个染色链都缩成一个点，此时只需要计算缩点后的有根树的拓扑序数量，这个部分可以直接树上背包解决。设当前已经处理的 $u$ 部分缩点后有 $i$ 个点，儿子结点 $v$ 为根的子树中缩点后有 $j$ 个点，则需要分类讨论：

• 若 $u,v$ 两点间的边染成灰色，则两个部分独立，合并后的排列数量需要乘 $\binom{i+j-1}j$。
• 否则，两个部分的链首尾拼接，合并后的排列数量需要乘以 ${\binom{i+j-2}{j-1}}$。

然后这个东西可以直接 $O(n^2)$ 求出来。设当前已经处理了一部分树的信息，且此时黑边形成若干个连通块，则显然要合并一个儿子结点，若连儿子的边不是黑边，则两个部分的连通块互不影响，权值直接相乘即可。而若连儿子的边是黑边，则两个部分分别有一个连通块需要合并，其权值需要先异或起来再和其他部分拼接相乘。因此可以想到把包含当前根结点 $u$ 的黑色连通块留起来先暂时不计算，其他连通块的权值先全都乘起来。然后把包含 $u$ 的黑色连通块的权值异或和，其他所有黑色连通块的权值的乘积以及对应的拓扑序数量和白边的容斥系数相乘就可以得到答案。

直接把异或和这个维度记到状态中肯定爆炸了，套路的考虑拆位，每次只在 dp 中记录一个位的异或即可。具体的转移不是重点而且写起来特别累所以这里就不写具体转移了。算法的时间复杂度为 $O(n^2\log V)$ 可以通过该题。