Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Root the tree. For a subtree, do not try to decide all final components at once. Keep exactly one “open” component: the one containing the subtree root. Everything already cut away inside the subtree must be valid.
If the XOR of the whole subtree of is , and the XOR of all already closed components inside it is , then the open component has XOR . That means the DP only needs to know the closed-components XOR, not the actual open component directly.
The only useful values of live in the XOR-span of the numbers . Compress that span with a linear basis, so every representable XOR becomes a mask of size at most .
For a child , if you keep edge , its contribution is just its DP state. If you cut the edge, the child’s open component must be one of the , and then the child’s total contribution to closed XOR becomes exactly . So all cut transitions add into one coordinate: .
Child merging is XOR convolution. Maintain every DP array after Walsh-Hadamard transform: merges become pointwise multiplication, and the “add into one coordinate” cut transition can be computed and applied in using the inverse-transform formula for one point.
Root the tree at vertex . For every vertex , let
.
The main trap is trying to track raw 30-bit XOR values, or tracking which exact values appeared. Both are the wrong level of detail. A subtree only cares about the XOR effect of components already cut away from its root component.
First compress values. Take a linear basis of the XOR-span of . Let its rank be , so there are only possible representable XORs. For a value in this span, write for its mask. For every allowed component value , define .
Now define the DP in original, untransformed form:
= the number of ways to cut edges completely inside such that every component not containing is already beautiful, and the XOR of all those closed components is the value represented by mask .
Then the still-open component containing has XOR
.
For a leaf before considering the parent edge, .
Consider a child of . After computing , the edge has two options.
If we do not cut it, the open component of merges upward, so the child contributes its mask normally.
If we cut it, the open component of must have XOR for some . Suppose after cutting this parent edge, the total XOR contributed by the entire child subtree to the closed side is . In coordinates this target is
.
If is outside the span, this cut is impossible. Otherwise, for the child to close with value , before closing it must have had closed-XOR mask . Therefore the cut transition is:
,
while the no-cut option contributes
.
So is the full contribution of child to its parent. Then
,
where is XOR convolution. Starting value is the delta array with at mask .
Doing these convolutions naively would be cooked. Use the Walsh-Hadamard transform. For XOR convolution,
.
So we store every DP array transformed. Combining children becomes pointwise multiplication.
It remains to apply the cut transition quickly in transformed form. Let be the array where is incremented for every . Then
.
If we know , then
.
Now adding to original coordinate changes the transform by
.
That is only per vertex.
At the root there is no parent edge to cut. We just need the root open component to be beautiful:
.
So for every , add the original DP value at
,
if that value is representable. Each such point is recovered from the transform by the inverse Walsh-Hadamard formula.
This also handles correctly: closing a zero-XOR component changes no coordinate, but it is still a different cut choice, so it adds ways into the same mask. Annoying little case, but not magic.
The complexity is time and memory, with . In the worst case this is about , which is exactly the intended scale.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 1000000007;
const int MAXM = 1 << 10;
int sgn[MAXM][MAXM];
ll mod_pow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
struct XorBasis {
int val[30]{};
int coord[30]{};
int rank = 0;
int add(int x) {
int mask = 0;
for (int bit = 29; bit >= 0; --bit) {
if (!((x >> bit) & 1)) continue;
if (val[bit]) {
x ^= val[bit];
mask ^= coord[bit];
} else {
val[bit] = x;
coord[bit] = 1 << rank;
mask ^= 1 << rank;
++rank;
break;
}
}
return mask;
}
int get(int x) const {
int mask = 0;
for (int bit = 29; bit >= 0; --bit) {
if (!((x >> bit) & 1)) continue;
if (!val[bit]) return -1;
x ^= val[bit];
mask ^= coord[bit];
}
return mask;
}
};
int main() {
setIO();
for (int p = 0; p < MAXM; ++p) {
for (int q = 0; q < MAXM; ++q) {
sgn[p][q] = __builtin_parity((unsigned)(p & q)) ? -1 : 1;
}
}
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> a(n), b(k);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
XorBasis basis;
vector<int> bCoord;
bCoord.reserve(k);
for (int x : b) bCoord.push_back(basis.add(x));
int M = 1 << basis.rank;
int invM = (int)mod_pow(M, MOD - 2);
vector<int> zhat(M, 0);
for (int q = 0; q < M; ++q) {
for (int c : bCoord) zhat[q] += sgn[c][q];
}
vector<int> parent(n, -2), order;
order.reserve(n);
parent[0] = -1;
order.push_back(0);
for (int it = 0; it < (int)order.size(); ++it) {
int u = order[it];
for (int v : g[u]) {
if (v == parent[u]) continue;
parent[v] = u;
order.push_back(v);
}
}
vector<int> sub = a;
for (int it = n - 1; it > 0; --it) {
int u = order[it];
sub[parent[u]] ^= sub[u];
}
vector<int> dp((size_t)n * M);
for (int it = n - 1; it >= 0; --it) {
int u = order[it];
int *cur = dp.data() + (size_t)u * M;
fill(cur, cur + M, 1);
for (int v : g[u]) {
if (parent[v] != u) continue;
int *child = dp.data() + (size_t)v * M;
for (int q = 0; q < M; ++q) {
cur[q] = (ll)cur[q] * child[q] % MOD;
}
}
if (parent[u] != -1) {
int p = basis.get(sub[u]);
if (p != -1) {
ll sum = 0;
for (int q = 0; q < M; ++q) {
sum += (ll)cur[q] * zhat[q] * sgn[p][q];
}
sum %= MOD;
if (sum < 0) sum += MOD;
int delta = sum * invM % MOD;
for (int q = 0; q < M; ++q) {
if (sgn[p][q] == 1) {
cur[q] += delta;
if (cur[q] >= MOD) cur[q] -= MOD;
} else {
cur[q] -= delta;
if (cur[q] < 0) cur[q] += MOD;
}
}
}
}
}
int *root = dp.data();
ll ans = 0;
for (int x : b) {
int p = basis.get(sub[0] ^ x);
if (p == -1) continue;
ll sum = 0;
for (int q = 0; q < M; ++q) {
sum += (ll)root[q] * sgn[p][q];
}
sum %= MOD;
if (sum < 0) sum += MOD;
ans += sum * invM % MOD;
if (ans >= MOD) ans -= MOD;
}
cout << ans % MOD << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 1000000007;
const int MAXM = 1 << 10;
int sgn[MAXM][MAXM];
ll mod_pow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
struct XorBasis {
int val[30]{};
int coord[30]{};
int rank = 0;
int add(int x) {
int mask = 0;
for (int bit = 29; bit >= 0; --bit) {
if (!((x >> bit) & 1)) continue;
if (val[bit]) {
x ^= val[bit];
mask ^= coord[bit];
} else {
val[bit] = x;
coord[bit] = 1 << rank;
mask ^= 1 << rank;
++rank;
break;
}
}
return mask;
}
int get(int x) const {
int mask = 0;
for (int bit = 29; bit >= 0; --bit) {
if (!((x >> bit) & 1)) continue;
if (!val[bit]) return -1;
x ^= val[bit];
mask ^= coord[bit];
}
return mask;
}
};
int main() {
setIO();
for (int p = 0; p < MAXM; ++p) {
for (int q = 0; q < MAXM; ++q) {
sgn[p][q] = __builtin_parity((unsigned)(p & q)) ? -1 : 1;
}
}
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> a(n), b(k);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
XorBasis basis;
vector<int> bCoord;
bCoord.reserve(k);
for (int x : b) bCoord.push_back(basis.add(x));
int M = 1 << basis.rank;
int invM = (int)mod_pow(M, MOD - 2);
vector<int> zhat(M, 0);
for (int q = 0; q < M; ++q) {
for (int c : bCoord) zhat[q] += sgn[c][q];
}
vector<int> parent(n, -2), order;
order.reserve(n);
parent[0] = -1;
order.push_back(0);
for (int it = 0; it < (int)order.size(); ++it) {
int u = order[it];
for (int v : g[u]) {
if (v == parent[u]) continue;
parent[v] = u;
order.push_back(v);
}
}
vector<int> sub = a;
for (int it = n - 1; it > 0; --it) {
int u = order[it];
sub[parent[u]] ^= sub[u];
}
vector<int> dp((size_t)n * M);
for (int it = n - 1; it >= 0; --it) {
int u = order[it];
int *cur = dp.data() + (size_t)u * M;
fill(cur, cur + M, 1);
for (int v : g[u]) {
if (parent[v] != u) continue;
int *child = dp.data() + (size_t)v * M;
for (int q = 0; q < M; ++q) {
cur[q] = (ll)cur[q] * child[q] % MOD;
}
}
if (parent[u] != -1) {
int p = basis.get(sub[u]);
if (p != -1) {
ll sum = 0;
for (int q = 0; q < M; ++q) {
sum += (ll)cur[q] * zhat[q] * sgn[p][q];
}
sum %= MOD;
if (sum < 0) sum += MOD;
int delta = sum * invM % MOD;
for (int q = 0; q < M; ++q) {
if (sgn[p][q] == 1) {
cur[q] += delta;
if (cur[q] >= MOD) cur[q] -= MOD;
} else {
cur[q] -= delta;
if (cur[q] < 0) cur[q] += MOD;
}
}
}
}
}
int *root = dp.data();
ll ans = 0;
for (int x : b) {
int p = basis.get(sub[0] ^ x);
if (p == -1) continue;
ll sum = 0;
for (int q = 0; q < M; ++q) {
sum += (ll)root[q] * sgn[p][q];
}
sum %= MOD;
if (sum < 0) sum += MOD;
ans += sum * invM % MOD;
if (ans >= MOD) ans -= MOD;
}
cout << ans % MOD << '\n';
}
}