传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5909

【题解】

设$f_{x,i}$表示以$x$节点的子树中，权值为$i$的子树个数，其中$x$必选。

那么有dp方程：$f_{x,i} = \sum_{y = son[x]} f_{x,i} + \sum_{j \oplus k = i}f_{x, j}f_{y, k}$

用FWT优化转移即可，复杂度$O(nmlogm)$。

# include

include

include

include

// # include

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e3 + , H = + ;
const int mod = 1e9+;

int n, L, w[N], inv2;
int f[N][H];
int ans[H];
int head[N], nxt[N + N], to[N + N], tot = ;
inline void add(int u, int v) {
++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}
inline void adde(int u, int v) {
add(u, v), add(v, u);
}

inline int pwr(int a, int b) {
int ret = ;
while(b) {
if(b&) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return ret;
}

int s[H], t[H];
inline void FWT(int *a, int op) {
if(op) {
for (int len = ; len <= L; len<<=) { int m = len >> ;
for (int *p = a; p != a+L; p += len) {
for (int k=; k> ;
for (int *p = a; p != a+L; p += len) {
for (int k=; k<m; ++k) {
int x = p[k], y = p[k+m];
p[k] = (x+y) % mod;
p[k+m] = (x-y+mod) % mod;
}
}
}
}
}

inline void FWT_combine(int *A, int *B) {
for (int i=; i<L; ++i) s[i] = A[i], t[i] = B[i];
FWT(s, ); FWT(t, );
for (int i=; i<L; ++i) s[i] = 1ll * s[i] * t[i] % mod;
FWT(s, );
for (int i=; i<L; ++i) (A[i] += s[i]) %= mod;
}

inline void dfs(int x, int fa = ) {
for (int j=; j<L; ++j) f[x][j] = ;
f[x][w[x]] = ;
for (int i=head[x]; i; i=nxt[i]) {
if(to[i] == fa) continue;
dfs(to[i], x);
FWT_combine(f[x], f[to[i]]);
}
for (int j=; j<L; ++j) (ans[j] += f[x][j]) %= mod;
}

inline void sol() {
tot = ;
memset(head, , sizeof head);
memset(ans, , sizeof ans);
cin >> n >> L;
for (int i=; i<=n; ++i) scanf("%d", w+i);
for (int i=, u, v; i<n; ++i) {
scanf("%d%d", &u, &v);
adde(u, v);
}
dfs();
printf("%d", ans[]);
for (int i=; i<L; ++i) printf(" %d", ans[i]);
puts("");
}

int main() {
int T; cin >> T;
inv2 = pwr(, mod-);
while(T--) sol();
return ;
}