Again Trees... (Easy Version)

Root the tree at vertex $1$. The main trap is trying to DP over every possible XOR of the component touching the current vertex. Those XORs are 30-bit values, so that plan blows up immediately. The useful observation is that we do not need to store that XOR directly.

For a vertex $v$, let $sub_v$ be the XOR of all $a_x$ in the subtree of $v$. During a rooted-tree DP, there is always one special component in this subtree: the component containing $v$. Call it the open component, because it may later merge with $v$'s parent. Every other component inside the subtree must already be valid.

Since every completed component has XOR equal to one of $b_1,\dots,b_k$, and $k \le 4$, we can store only parities. For a mask $m$, define

$val[m]=\bigoplus_{i: \text{bit } i \text{ is set in } m} b_i.$

Now define $dp_v[m]$ as the number of ways to cut edges completely inside the subtree of $v$ such that:

• every component not containing $v$ is already valid;
• among those completed components, bit $i$ of $m$ is the parity of the number of components whose XOR is $b_i$.

Then the XOR of the open component is not extra state. It is forced:

$open(v,m)=sub_v \oplus val[m].$

Why? The XOR of the whole subtree equals the XOR of all completed components plus the XOR of the open component. The completed components contribute exactly $val[m]$, because equal values cancel in pairs under XOR. So the open component must be $sub_v \oplus val[m]$. Nice little bitmask robbery.

For a leaf, there are no completed components yet, so $dp_v[0]=1$.

Now process children one by one. Suppose we are combining vertex $v$ with a child $u$. Take an existing state $p$ for the processed part of $v$, and a state $q$ from the child subtree.

There are exactly two choices for the edge $(v,u)$.

First, keep the edge. Then the child's open component merges into $v$'s open component. No new completed component is created, so the completed-component parity mask becomes

$p \oplus q.$

So we add

$dp_v[p] \cdot dp_u[q]$

to the new state $p \oplus q$.

Second, cut the edge. Then the child's open component becomes a completed component, so it must be valid. Its XOR is

$open(u,q)=sub_u \oplus val[q].$

If this equals some $b_j$, then cutting is legal, and we must also toggle bit $j$ because we just added one completed component of type $b_j$. The new mask is

$p \oplus q \oplus 2^j.$

If $open(u,q)$ is not in $b$, that cut choice is illegal.

After all children are merged, $dp_v$ is complete. At the root, the open component also has to become a real component, so for each mask $m$ we check whether

$sub_{root} \oplus val[m]$

belongs to $b$. If yes, add $dp_{root}[m]$ to the answer.

This counts every edge set exactly once: each edge is processed at its parent, and the transition chooses either cut or keep. The validity condition is checked exactly when a component becomes closed: either when a child edge is cut, or at the root for the final open component. No hidden double-counting, no magic, no nonsense.

A small implementation detail: keep masks by indices of $b_i$, not by compressed XOR values. This stays clean even when $0$ is in $b$ or different masks have the same XOR value.

There are at most $2^k \le 16$ masks. Each edge combines two mask arrays, so the complexity is

$O(n \cdot 4^k),$

which is at most about $256n$. Memory is $O(n \cdot 2^k)$.