← 返回题目列表

Codeforces · 2194/F2

F2. 再次树...(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的差异在于,在此版本中,$$$k \leq 10$$$。只有解决了该问题的所有版本,您才能破解。

给定一棵由 $$$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 \lt 2^{30}$$$) - 写在顶点上的值。

以下行包含 $$$k$$$ 不同的整数 $$$b_1, b_2, \ldots, b_k$$$ ($$$0 \leq b_i \lt 2^{30}$$$) — 集合 $$$b$$$ 的元素。

保证所有数据集的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试数据集,输出一个整数 - 问题的答案。

示例

输入
复制

4
5 1
1 2
1 3
3 4
2 5
0 2 2 3 3
1
5 1
4 5
1 2
3 1
3 5
0 0 2 0 2
0
5 2
1 2
1 3
3 4
2 5
0 2 2 3 3
1 3
4 1
1 2
2 3
3 4
1 1 1 1
1

输出
复制

2
8
4
3

注意

第一个测试数据集的插图。在其中,您可以删除顶点 $$$1$$$ 和 $$$2$$$ 之间的边。那么顶点 $$$2$$$ 和 $$$5$$$ 组成的分量中的按位异或为 $$$a_2 \oplus a_5 = 2 \oplus 3 = 1$$$。具有顶点 $$$1$$$、$$$3$$$ 和 $$$4$$$ 的分量中的按位异或为 $$$a_1 \oplus a_3 \o​​plus 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)]$$$。