#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 1e9 + 10;
const int N = 1e6 + 10;
int c[N];
vector<int> g[N];
int dp[N][2];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }
}

void dfs(int v, int p, int k, int& ans) {
    dp[v][0] = -inf;
    dp[v][1] = -inf;
    dp[v][c[v] & 1] = c[v];
    for (int to : g[v]) {
        if (to != p) {
            dfs(to, v, k, ans);
            int res[2] = {dp[v][0], dp[v][1]};
            for (int i = 0; i <= 1; i++) {
                for (int j = 0; j <= 1; j++) {
                    res[i ^ j] = max(res[i ^ j], dp[v][i] + dp[to][j]);
                }
            }
            dp[v][0] = res[0];
            dp[v][1] = res[1];
        }
    }
    if (dp[v][k & 1] >= k) {
        ans++;
        dp[v][0] = -inf;
        dp[v][1] = -inf;
    }
}

int solve(int n, int k) {
    int ans = 0;
    dfs(1, 1, k, ans);
    return ans;
}

bool getbit(int mask, int bit) {
    return mask & (1 << bit);
}

int slow(int n, int k) {
    vector<int> adj(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j : g[i]) {
            adj[i] |= (1 << (j - 1));
        }
    }
    vector<bool> is_connected((1 << n), false);
    for (int mask = 1; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) == 1) {
            is_connected[mask] = true;
        } else {
            for (int i = 1; i <= n; i++) {
                if (getbit(mask, i - 1)) {
                    int nxt = mask ^ (1 << (i - 1));
                    if (is_connected[nxt] && (nxt & adj[i]) != 0) {
                        is_connected[mask] = true;
                    }
                }
            }
        }
    }
    vector<int> sum((1 << n), 0);
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 1; i <= n; i++) {
            if (getbit(mask, i - 1)) {
                sum[mask] += c[i];
            }
        }
    }
    vector<int> dp((1 << n), 0);
    for (int mask = 1; mask < (1 << n); mask++) {
        for(int submask = mask; submask >= 0; submask = (submask - 1) & mask){
            if (sum[submask] == k && is_connected[submask]) {
                dp[mask] = max(dp[mask], dp[mask ^ submask] + 1);
            }
            if (submask == 0) {
                break;
            }
        }
    }
    return dp[(1 << n) - 1];
}

void stress() {
    mt19937 rnd;
    while (true) {
        int n = rnd() % 10 + 1;
        int k = rnd() % 10 + 1;
        init(n);
        for (int i = 1; i <= n; i++) {
            c[i] = rnd() % 3;
        }
        for (int i = 2; i <= n; i++) {
            int j = rnd() % (i - 1) + 1;
            g[i].push_back(j);
            g[j].push_back(i);
        }

        int ans = solve(n, k);
        int res = slow(n, k);

        if (ans == res) {
            cout << "OK" << endl;
        } else {
            cout << "WA\n";
            cout << "1\n";
            cout << n << " " << k << "\n";
            for (int i = 1; i <= n; i++) {
                cout << c[i] << " ";
            }
            cout << "\n";
            for (int i = 1; i <= n; i++) {
                for (int j : g[i]) {
                    if (i < j) {
                        cout << i << " " << j << "\n";
                    }
                }
            }
            cout << "\n";
            cout << ans << " " << res << "\n";
            break;
        }
    }
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    // stress();

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        init(n);
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
        }
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        cout << solve(n, k) << "\n";
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}