Again Trees... (Easy Version)

Again Trees... (Easy Version)

Problem

给定一个包含 \(n\) 个结点的树，每个结点都写有一个非负整数 \(a_v\)。

另外，还给定 \(k\) 个互不相同的非负整数 \(b_1,\dots,b_k\)。

我们称一个边集是“美丽的”，如果把这些边从树中移除后，树被分成若干连通块，并且每个连通块内所有结点 \(a_v\) 的按位异或值属于集合 \(b\)。

你需要计算树中美丽的边集有多少个，结果对 \(10^9 + 7\) 取模。

数据范围： - \(2 \le n \le 10^5\) - \(1 \le k \le 4\)

Solution

一个很朴素的想法是开值域

\(f_{u,v}\) 表示 \(u\) 所在的连通块异或和为 \(v\) 的方案数

显然是开不下的

一个很精妙的状态是

\(f_{u,s}\) 表示以 \(u\) 为根的子树除去 \(u\) 所在连通块其他连通块的值对应的的 \(b\) 的组合

注意这里的 \(s\) 是 \(b_i\) 的编号，用二进制压缩

显然其他连通块的值一定在 \(b\) 中

考虑转移

对于 \(u\) 来说，有边 \(u \to v\)，考虑断与不断这条边

• 不断

  \[f_{u,S \oplus T} = f_{u,S \oplus T} + f'_{u, S} \times f_{v, T} \]

  注意，对于 \(u\) 来说有很多个 \(v\) （子节点）

  为了避免后效性

  每次要先存一个 \(f'\) 表示原来的 \(f\) 数组，再进行转移

  \(S \oplus T\) 相当于将原来的其他连通块与新的连通块进行合并

  注意 \(S\) 的其他连通块和 \(T\) 的其他连通块是不相交的

  因为 \(T\) 相当于是新加入的一颗子树

• 断

  定义 \(res\) 为 \(T\) 的 \(b\) 的组合所对应的异或和，\(sub\) 为 \(u\) 子树的异或和

  当 \(sub \oplus res = b_x\) 时有转移

  \(sub \oplus res\) 相当于减去其他连通块 得到 \(v\) 所在连通块的异或和

  \[f_{u,S \oplus T \oplus x} = f_{u,S \oplus T \oplus x} + f'_{u, S} \times f_{v, T} \]

  观察到就只多了一个 \(x\)，相当增加了 \(v\) 所在的连通块

Code

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 10, K = 5, p = 1e9 + 7;
int t, n, k, a[N], b[K], f[N][1 << K], s[N], tmp[1 << K];
vector <int> e[N];
void dfs(int u, int fa) {
	s[u] = a[u], f[u][0] = 1;
	for (auto v : e[u]) {
		if (v == fa) continue;
		dfs(v, u);
		s[u] ^= s[v];
		for (int S = 0; S < 1 << k; S++) tmp[S] = f[u][S], f[u][S] = 0;
		for (int S = 0; S < 1 << k; S++) 
			for (int T = 0; T < 1 << k; T++) f[u][S ^ T] += tmp[S] * f[v][T] % p, f[u][S ^ T] %= p;
		for (int S = 0; S < 1 << k; S++) 
			for (int T = 0; T < 1 << k; T++) {
				int res = s[v];
				for (int i = 0; i < k; i++) if (T >> i & 1) res ^= b[i + 1]; 
				for (int i = 0; i < k; i++) if (res == b[i + 1]) {f[u][S ^ T ^ (1 << i)] += tmp[S] * f[v][T] % p, f[u][S ^ T ^ (1 << i)] %= p; break;} 
			}
	}
}
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) for (int S = 0; S < 1 << k; S++) f[i][S] = 0;
	for (int i = 1; i <= n; i++) e[i].clear();
	for (int u, v, i = 1; i < n; i++) cin >> u >> v, e[u].emplace_back(v), e[v].emplace_back(u);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= k; i++) cin >> b[i];
	dfs(1, 0);
	int ans = 0;
	for(int S = 0 ; S < 1 << k; S++){
		int res = s[1];
		for (int i = 0; i < k; i++) if (S >> i & 1) res ^= b[i + 1]; 
		for (int i = 0; i < k; i++) if (res == b[i + 1]) {ans += f[1][S]; ans %= p; break;}
	}
	cout << ans << '\n';
}
signed main() {
	cin.tie(nullptr) -> ios::sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}