Description：

一棵树，节点的权值 $\in[0,m)$ 。对每个 $v\in[0,m)$ ，求出权值为 $v$ 的连通块个数。

$1\leqslant n\leqslant 1000,1\leqslant m\leqslant 1000$

Solution：

首先可以用类似切树游戏那道题的做法用 $FWT$ 维护树形 $DP$ ，但是还有一个更好写的做法，就是类似 $shopping$ 那道题的做法，用点分治来维护树形依赖关系的背包问题，然后在 $dfs$ 序上 $DP$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1050

#define MOD 1000000007

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int siz[MAXN],d[MAXN],root,s;

#define INF 0x3f3f3f3f

bool vis[MAXN];

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa || vis[e[i].to])continue;

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

int dfn[MAXN],st[MAXN],ed[MAXN],tot = 0;

void dfs(int k,int fa)

{

	st[k] = ++tot;dfn[tot] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		dfs(e[i].to,k);

	}

	ed[k] = tot;

	return;

}

int f[MAXN][MAXN];

int ans[MAXN];

void calc(int k)

{

	tot = 0;

	dfs(k,0);

	memset(f[tot + 1],0,sizeof(f[tot + 1]));

	f[tot + 1][0] = 1;

	for(int i = tot;i >= 1;--i)

	{

		memset(f[i],0,sizeof(f[i]));

		int v = dfn[i];

		for(int j = 0;j < m;++j)f[i][j] = (f[i][j] + f[ed[v] + 1][j]) % MOD;

		for(int j = 0;j < m;++j)f[i][j] = (f[i][j] + f[i + 1][j ^ val[v]]) % MOD;

	}

	f[1][0] = (f[1][0] - 1 + MOD) % MOD;

	for(int j = 0;j < m;++j)ans[j] = (ans[j] + f[1][j]) % MOD;

	return;

}

void divide(int k)

{

	calc(k);

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		root = 0;s = siz[e[i].to];

		getroot(e[i].to,k);

		divide(root);

	}

	return;

}

void work()

{

	edgenum = 0;

	memset(lin,0,sizeof(lin));

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	memset(vis,0,sizeof(vis));

	root = 0;d[0] = INF;s = n;

	memset(ans,0,sizeof(ans));

	getroot(1,0);

	divide(root);

	for(int j = 0;j < m - 1;++j)printf("%d ",ans[j]);

	printf("%d\n",ans[m - 1]);

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}