← 返回题目
题库练习 Again Trees... (hard version)
← 上一题 下一题 →

A16766 | Again Trees... (hard version)

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

这是该问题的困难版本。不同之处在于本版本中 $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
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
输出 #1
2
8
4
3
C++ 编辑器
输入
输出