题解：CF599E Sandy and Nuts

$n \leq 13$，显然状压。

设 $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$ 必须包含此节点就能解决算重的问题。

此时，我们需考虑转移的限制。

把不合法的状态剪去即可。

代码上可用记搜实现，具体地，想要获得 $T$ 要枚举 $S$ 的子集。有经典套路可做到 $O(3^n)$ 而不是 $O(4^n)$。

还要注意一点，在搜索时先把 $u$ 的状态从 $S$ 里面扣掉，这样就能避免一坨边界讨论。往下递归的时候把 $u$ 的状态再加进去就行了。

于是做完了，时间复杂度 $O(3^n n(n+m+q))$。实际上由于无用状态极多，三秒时限完全卡不满。