A16765. Again Trees... (Easy Version)
编程题
提高+/省选-
知识点
题目描述
这是本题的简单版本。各版本的区别在于本版本中 $k \leq 4$。只有在你解决了本题所有版本后才能进行 hack。
给定一个包含 $n$ 个结点的树。每个结点都写有一个非负整数 $a_v$。另外，还给定 $k$ 个互不相同的非负整数 $b_1, \ldots, b_k$。
我们称一个边集是“美丽的”，如果把这些边从树中移除后，树被分成若干连通块，并且每个连通块内所有结点 $a_v$ 的按位异或值属于集合 $b$。
你需要计算树中美丽的边集有多少个，结果对 $10^9+7$ 取模。
给定一个包含 $n$ 个结点的树。每个结点都写有一个非负整数 $a_v$。另外，还给定 $k$ 个互不相同的非负整数 $b_1, \ldots, b_k$。
我们称一个边集是“美丽的”，如果把这些边从树中移除后，树被分成若干连通块，并且每个连通块内所有结点 $a_v$ 的按位异或值属于集合 $b$。
你需要计算树中美丽的边集有多少个，结果对 $10^9+7$ 取模。
输入格式
每个测试点包含多组数据。第一行包含测试组数 $t$（$1 \leq t \leq 500$）。每组数据的描述如下。
每组数据的第一行为两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$1 \leq k \leq 4$），分别表示树的结点数和集合 $b$ 的大小。
接下来 $n-1$ 行，每行两个整数 $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$。
每组数据的第一行为两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$1 \leq k \leq 4$），分别表示树的结点数和集合 $b$ 的大小。
接下来 $n-1$ 行，每行两个整数 $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
说明/提示
以下是第一个测试点的示意图。在这个点中，你可以移除结点 $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)]$。
在第三个测试点，美丽的边集包括（用边连接的顶点对表示）：$[(1, 2)], [(1, 3)], [(2, 5)], [(3, 4)]$。注意，前两个样例仅仅集合 $b$ 不同。
在第四个测试点，美丽的边集为：$[(1, 2)], [(3, 4)], [(1, 2), (2, 3), (3, 4)]$。