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

A16765 | Again Trees... (Easy Version)

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

题目描述

这是本题的简单版本。各版本的区别在于本版本中 $k \leq 4$。只有在你解决了本题所有版本后才能进行 hack。

给定一个包含 $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$。

输出格式

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

输入输出样例

输入 #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++ 编辑器
输入
输出