思路

不太一样的做法。

直接爆搜每条边的颜色复杂度是 2n2^n，我们可以尝试折半搜索然后合并答案。

具体地，把 n−1n-1 条边分成两半，分别搜索每条边染黑还是白，搜索结果是一个二进制数，第 ii 位是否为 11 代表是否满足第 ii 个条件的限制。O(1)\mathcal{O}(1) 检查是否满足条件可以先预处理每个条件所包含的边集 EiE_i，然后再把搜索出来的边集 SS 与 EiE_i 做按位与即可，这部分预处理时间复杂度为 O(nm)\mathcal{O(nm)}，搜索时间复杂度为 O(2n2m)\mathcal{O}(2^{\frac{n}{2}}m)。

搜索完之后我们得到了两个二进制数组成的集合，分别代表前 n−12\frac{n-1}{2} 条边染色后满足条件的情况和后 n−12\frac{n-1}{2} 条边的情况。可以考虑对于第一个集合里的每个元素分别计算可以和多少个第二个集合里的元素配对。两个状态 a,ba,b 可以配对当且仅当 aor⁡b=2m−1a\operatorname{or} b=2^m-1，此处 or⁡\operatorname{or} 代表按位或。容易发现这个条件可以转换为 bb 按位取反后是 aa 的子集，把第二个集合中的元素全部按位取反后的集合叫作 SS，此时问题就变成了多次询问集合 SS 中有多少个元素是 xx 的子集，可以用高维前缀和 O(2mm)\mathcal{O}(2^mm) 解决。

总时间复杂度 O((2n2+2m)m)\mathcal{O}((2^\frac{n}{2}+2^m)m)，可以通过。

代码

link