F1. Again Trees... (Easy Version)
Q：给定一棵大小为 \(n\) 的树，每个点 \(u\) 都有权值 \(a_{u}\)；并给定一个大小为 \(k\) 的数集 \(b\)。计算删除边的某个子集的方案数，要求满足：删除该子集的所有边后，剩下的每个连通块的权值异或和均 \(\in b\)。
\(n \le 10^{5}\)，\(k \le 4\)
显然是一道树形 dp 计数题。由于 \(k\) 特别小，我们可以考虑将 \(b\) 设置为 dp 状态。
预处理 \(sub\_b\)，共 \(2^{k}\) 个取值，表示 \(b\) 的某个下标子集对应的异或和。
考虑子树 \(u\) 的所有分割方案，要求除了点 \(u\) 所在的连通块外，其他所有连通块的异或和均 \(\in b\)。那么，点 \(u\) 所在的连通块异或和取值一定可以用某个 \(s_{u} \oplus sub\_b[j]\) 表示，\(s_{u}\) 即子树 \(u\) 的异或和。
于是我们可以定义状态：
状态定义
\(dp_{u,j}\) 表示考虑子树 \(u\)，删除子树 \(u\) 内所有边的某个子集后，点 \(u\) 所在连通块的异或和为 \(s_{u} \oplus sub\_b_{j}\)，且切分的其他连通块异或和取值均 \(\in b\)，切分方案数。
状态转移
考虑合并子树 \(v\)，只需决策边 \((u, v)\) 是否删除。
设合并（转移）前，子树 \(u,v\) 的异或和分别为 \(s_{u}, s_{v}\)，用 \(j, jj\) 分别枚举点 \(u, v\) 所在连通块的异或和状态（即 \(s_{u} \oplus sub\_b_{j}\)，\(s_{v}\oplus sub\_b_{jj}\)）。
若删除 \((u, v)\)，则需要保证删除后点 \(v\) 所在连通块的异或和 \(\in b\)；若不删除 \((u, v)\)，则可以直接无条件转移（因为二者均无需保证点 \(u\) 所在连通块的异或和 \(\in b\)，只需要保证其他连通块的异或和 \(\in b\)）。
具体状态转移部分以及答案计算见 code。总复杂度 \(O(n * 2^{k} * 2^{k} * k)\)。
code