Tree Cutting

Byteasar has a tree $T$ with $n$ vertices conveniently labeled with $1,2,...,n$. Each vertex of the tree has an integer value $v_i$.

The value of a non-empty tree $T$ is equal to $v_1\oplus v_2\oplus ...\oplus v_n$, where $\oplus$ denotes bitwise-xor.

Now for every integer $k$ from $[0,m)$, please calculate the number of non-empty subtree of $T$ which value are equal to $k$.

A subtree of $T$ is a subgraph of $T$ that is also a tree.

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.

In each test case, the first line of the input contains two integers $n(n\leq 1000)$ and $m(1\leq m\leq 2^{10})$, denoting the size of the tree $T$ and the upper-bound of $v$.

The second line of the input contains $n$ integers $v_1,v_2,v_3,...,v_n(0\leq v_i < m)$, denoting the value of each node.

Each of the following $n-1$ lines contains two integers $a_i,b_i$, denoting an edge between vertices $a_i$ and $b_i(1\leq a_i,b_i\leq n)$.

It is guaranteed that $m$ can be represent as $2^k$, where $k$ is a non-negative integer.

For each test case, print a line with $m$ integers, the $i$-th number denotes the number of non-empty subtree of $T$ which value are equal to $i$.

The answer is huge, so please module $10^9+7$.

2
4 4
2 0 1 3
1 2
1 3
1 4
4 4
0 1 3 1
1 2
1 3
1 4

3 3 2 3
2 4 2 3

BestCoder Round #88