资讯详情

F1. Again Trees... (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, $k \leq 4$. You can hack only if you solved all versions of this problem.

Given a tree consisting of $n$ vertices. Each vertex has a non-negative integer $a_v$ written on it. You are also given $k$ distinct non-negative integers $b_1, \ldots, b_k$.

We will call a set of edges beautiful if, after removing these edges from the tree, the tree splits into connected components, where in each component the bitwise XOR of all the numbers $a_v$ in that component belongs to the set $b$.

You need to count the number of beautiful sets of edges in the tree modulo $10^9 + 7$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each dataset contains two integers $n$ and $k$ ($2 \leq n \leq 10^5$, $1 \leq k \leq 4$) — the number of vertices in the tree and the size of the set $b$.

The next $n - 1$ lines describe the edges of the tree. The $i$-th line contains two integers $v_i$ and $u_i$ ($1 \leq v_i, u_i \leq n$) — the numbers of the vertices connected by the $i$-th edge.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 2^{30}$) — the values written on the vertices.

The following line contains $k$ distinct integers $b_1, b_2, \ldots, b_k$ ($0 \leq b_i \lt 2^{30}$) — the elements of the set $b$.

It is guaranteed that the sum of $n$ across all datasets does not exceed $10^5$.

Output

For each test dataset, output a single integer — the answer to the problem.

Example

Input

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

Output

2
8
4
3

Note

Illustration for the first test dataset. In it, you can remove the edge between vertices $1$ and $2$. Then the bitwise XOR in the component consisting of vertices $2$ and $5$ is $a_2 \oplus a_5 = 2 \oplus 3 = 1$. The bitwise XOR in the component with vertices $1$, $3$, and $4$ is $a_1 \oplus a_3 \oplus a_4 = 0 \oplus 2 \oplus 3 = 1$. The second beautiful set is the one consisting of the edge connecting vertices $1$ and $3$.

In the third test dataset, the beautiful sets will be (an edge is denoted by the pair of vertices it connects) $[(1, 2)], [(1, 3)], [(2, 5)], [(3, 4)]$. Note that the first and third samples differ only in the set $b$.

In the fourth test dataset, the beautiful sets will be $[(1, 2)], [(3, 4)], [(1, 2), (2, 3), (3, 4)]$.

 

解题思路

  本题的难点在于 dp 的状态定义不好想。通常的思路是定义 $f(u,s)$ 表示以 $u$ 为根的子树中，$u$ 所在连通块的异或和为 $s$，且其余所有连通块的异或和均属于集合 $b$ 时的方案数。但由于 $a_i$ 的取值范围很大，导致 $s$ 的状态空间也很大，时间和空间复杂度都会爆掉。

  在上述定义中，子树 $u$ 中其余连通块的异或和必须属于集合 $b$ ，而 $u$ 所在连通块的异或和可以是任意值。考虑到集合 $b$ 的大小很小（最大为 $4$），包含的状态有限，我们可以转换思路：将状态 $s$ 用来表示子树 $u$ 中其余连通块的状态，而非 $u$ 所在连通块的状态。

  引入异或的相关性质（可参考线性基），定义 $S$ 为 $b$ 的所有 $2^{|b|}$ 个子集的异或和构成的集合。由异或运算的性质可知，$S$ 对异或运算封闭，即对于任意 $x, y \in S$ 均有 $x \oplus y \in S$。由于我们只关心子树中其余连通块的异或和是否属于 $b$，而这些异或和的总异或和必然属于 $S$。因此，我们可以用 $|S| \leq 2^4$ 个状态来表示子树中其余连通块的状态。而 $u$ 所在连通块的异或和可以通过子树总异或和 $s_u$，与子树中其余连通块异或和 $s$ 异或得到，即 $s_u \oplus s$。

  重新定义状态 $f(u,i,s)$ 表示以 $u$ 为根的前 $i$ 棵子树中，除了 $u$ 所在连通块，其余连通块的异或和均属于集合 $b$，且这些异或和的总异或和为 $s$ 时的方案数。记 $u$ 的子节点个数为 $m_u$，则 $f(u, m_u, s)$ 即为处理完所有子树 $u$ 后的方案数。转移时考虑是否保留 $u$ 与子节点 $v_i$ 的连边 $(u,v_i)$，设子节点 $v_i$ 传递上来的状态为 $t$（即 $f(v_i, m_{v_i}, t)$）：

• 保留边 $(u, v_i)$：此时 $u$ 与 $v_i$ 处于同一连通块。$v_i$ 子树中的其余连通块将并入子树 $u$ 的其余连通块中。由乘法原理，从状态 $f(u, i-1, s \oplus t \in S)$ 转移而来，方案数贡献为 $f(u, i-1, s \oplus t) \cdot f(v_i, m_{v_i}, t)$。
• 移除边 $(u, v_i)$：此时 $v_i$ 所属连通块独立出来。这要求 $v_i$ 所在连通块的异或和 $s_{v_i} \oplus t$ 属于集合 $b$。同时，这些连通块并入子树 $u$ 的其余连通块后，总的异或和变化为 $(s_{v_i} \oplus t) \oplus t = s_{v_i}$。因此需满足 $s \oplus s_{v_i} \in S$，并从 $f(u, i-1, s \oplus s_{v_i})$ 转移而来，方案数贡献为 $f(u, i-1, s \oplus s_{v_i}) \cdot f(v_i, m_{v_i}, t)$。

  综上所述，转移方程为：$$f(u,i,s) = \sum_{t \in S}{f(u,i-1,s \oplus t) \cdot f(v_i,m_{v_i},t)} + \sum_{\begin{array}{} t \in S \\ s_{v_i} \oplus t \in b \\ s \oplus s_{v_i} \in S \end{array}}{f(u,i-1,s \oplus s_{v_i}) \cdot f(v_i, m_{v_i}, t)}$$

  最终统计答案时，需要满足根节点所在连通块的异或和也属于 $b$。若整棵树以 $r$ 为根，即答案为：$$\sum_{\begin{array}{} t \in S \\ s_r \oplus t \in b \end{array}}{f(r,m_r,t)}$$

  AC 代码如下，时间复杂度为 $O(n \cdot 4^{k} \cdot k)$（若使用哈希表优化集合 $b$ 的查找可优化到 $O(n \cdot 4^{k})$）：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int mod = 1e9 + 7;void solve() {int n, m;cin >> n >> m;vector<vector<int>> g(n + 1);for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}vector<int> a(n + 1), b(m), c(1 << m);for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 0; i < m; i++) {cin >> b[i];}for (int i = 0; i < 1 << m; i++) {for (int j = 0; j < m; j++) {if (i >> j & 1) c[i] ^= b[j];}}sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());sort(c.begin(), c.end());c.erase(unique(c.begin(), c.end()), c.end());unordered_map<int, int> mp;for (int i = 0; i < c.size(); i++) {mp[c[i]] = i;}vector<int> s(n + 1);vector<vector<int>> f(n + 1, vector<int>(c.size()));auto dfs = [&](auto &&dfs, int u, int p) -> void {f[u][0] = 1;s[u] = a[u];for (auto &v : g[u]) {if (v == p) continue;dfs(dfs, v, u);vector<int> g(c.size());for (int j = 0; j < c.size(); j++) {for (int k = 0; k < c.size(); k++) {int t = mp[c[j] ^ c[k]];g[j] = (g[j] + 1ll * f[u][t] * f[v][k]) % mod;if (find(b.begin(), b.end(), s[v] ^ c[k]) != b.end() && mp.count(c[j] ^ s[v])) {t = mp[c[j] ^ s[v]];g[j] = (g[j] + 1ll * f[u][t] * f[v][k]) % mod;}}}f[u] = g;s[u] ^= s[v];}};dfs(dfs, 1, 0);int ret = 0;for (int i = 0; i < c.size(); i++) {if (find(b.begin(), b.end(), s[1] ^ c[i]) != b.end()) ret = (ret + f[1][i]) % mod;}cout << ret << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

 

参考资料

  Codeforces Round 1078 (Div. 2) A,B,C,D,E,F1个人题解：https://www.cnblogs.com/CUC-MenG/p/19605002

  Codeforces Round #1078 Editorial：https://codeforces.com/blog/entry/150940