CF2194F2 Again Trees... (hard version)

这是该问题的困难版本。不同之处在于本版本中 $k \leq 10$。只有在你完成了所有版本的本题后，才可以进行 hack。 给定一棵包含 $n$ 个顶点的树。每个顶点上写有一个非负整数 $a_v$。同时给定 $k$ 个互不相同的非负整数 $b_1, \ldots, b_k$。 我们称一组边为美丽的，如果在移除这些边后，树被分成若干连通块，并且每个连通块内所有顶点的数 $a_v$ 的按位异或值属于集合 $b$。 你需要计算该树中美丽的边集的数量，对 $10^9 + 7$ 取模。

每个测试数据包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 500$）。随后是各个测试用例的描述。 每组数据的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$1 \leq k \leq 10$）——树上的顶点数和集合 $b$ 的大小。 接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq n$）——表示第 $i$ 条边连接的两个顶点。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i < 2^{30}$）——每个顶点上的值。 最后一行包含 $k$ 个互不相同的整数 $b_1, b_2, \ldots, b_k$（$0 \leq b_i < 2^{30}$）——集合 $b$ 中的元素。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示美丽边集的数量。

下图为第一个测试用例的示意图。在该示例中，你可以删除顶点 $1$ 和 $2$ 之间的边。此时，由顶点 $2$ 和 $5$ 组成的连通块的异或值为 $a_2 \oplus a_5 = 2 \oplus 3 = 1$。由顶点 $1$、$3$ 和 $4$ 组成的连通块的异或值为 $a_1 \oplus a_3 \oplus a_4 = 0 \oplus 2 \oplus 3 = 1$。第二种美丽集合是只删除连接顶点 $1$ 和 $3$ 的那条边。  在第三个测试用例中，美丽边集为（用一对顶点表示边）：$[(1, 2)], [(1, 3)], [(2, 5)], [(3, 4)]$。注意前两个样例唯一不同之处是集合 $b$。 在第四个测试用例中，美丽边集为：$[(1, 2)], [(3, 4)], [(1, 2), (2, 3), (3, 4)]$。 由 ChatGPT 5 翻译