题解：CF599E Sandy and Nuts

· · 题解

设 $dp_{u,S}$ 表示以 $u$ 为根，这个子树的点集为 $S$ 的方案数。显然有转移：$dp_{u,S} = \sum \limits_{T \subseteq S,v\in E_u}dp_{v,T} \times dp_{u,S-T}$。（这里的减号是差集，在实操的时候要异或） 这时候我们发现会算重。具体而言，我们会在按照不同的顺序枚举同一个子树。因此，考虑限定枚举顺序。随意取出一个异于根节点的点，钦定 $T$ 必须包含此节点就能解决算重的问题。 此时，我们需考虑转移的限制。 - $\text{LCA}$ 的限制 - 如果对于一条限制 $(a,b,c)$，满足 $c=u$ 且 $a,b \in T$，显然不合法。 - 如果对于一条限制 $(a,b,c)$，满足 $c \in T$ 且 $a \notin T \lor b \notin T$，显然不合法。 - 边的限制 - 如果有大于一条边 $(a,b)$，满足 $a = u \land b \in T$，显然不合法。 - 如果有一条边 $(a,b)$，满足 $x,y \neq u \land a\in T \land b \notin T$，显然不合法。 把不合法的状态剪去即可。 代码上可用记搜实现，具体地，想要获得 $T$ 要枚举 $S$ 的子集。有经典套路可做到 $O(3^n)$ 而不是 $O(4^n)$。 还要注意一点，在搜索时先把 $u$ 的状态从 $S$ 里面扣掉，这样就能避免一坨边界讨论。往下递归的时候把 $u$ 的状态再加进去就行了。 于是做完了，时间复杂度 $O(3^n n(n+m+q))$。实际上由于无用状态极多，三秒时限完全卡不满。 [参考代码。](https://www.luogu.com.cn/paste/uzcq4eo7)