#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll; 
 
vector<vector<ll>> dp;
ll n, d;
 
void dfs(ll node, ll parent, const vector<ll>& used, const vector<vector<ll>>& G, const vector<ll>& a) {
    ll sum_not_chosen = 0;
    ll sum_chosen = a[node];
 
    for (auto u : G[node]) {
        if (u != parent) {
            dfs(u, node, used, G, a);
            sum_not_chosen += max(dp[u][1], dp[u][0]);
            sum_chosen += max(dp[u][1] - 2 * d, dp[u][0]);
        }
    }
 
    dp[node][1] = sum_chosen; 	
    dp[node][0] = sum_not_chosen;	
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    ll t;
    if (cin >> t) {
        while (t--) {
            cin >> n >> d;
 
            vector<ll> a(n + 1, 0); 
            for (ll i = 1; i <= n; i++) {
                cin >> a[i];
            }
 
            vector<vector<ll>> G(n + 1); 
            for (ll i = 1; i <= n - 1; i++) {
                ll u, v;
                cin >> u >> v; 
                G[u].push_back(v);
                G[v].push_back(u); 
            }
 
            dp.assign(n + 5, vector<ll>(2, 0));
            vector<ll> used(n + 1, 0); 
 
            dfs(1, 0, used, G, a);
 
            cout << max(dp[1][1], dp[1][0]) << "\n";
        }
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgbGw7IAoKdmVjdG9yPHZlY3RvcjxsbD4+IGRwOwpsbCBuLCBkOwoKdm9pZCBkZnMobGwgbm9kZSwgbGwgcGFyZW50LCBjb25zdCB2ZWN0b3I8bGw+JiB1c2VkLCBjb25zdCB2ZWN0b3I8dmVjdG9yPGxsPj4mIEcsIGNvbnN0IHZlY3RvcjxsbD4mIGEpIHsKICAgIGxsIHN1bV9ub3RfY2hvc2VuID0gMDsKICAgIGxsIHN1bV9jaG9zZW4gPSBhW25vZGVdOwogICAKICAgIGZvciAoYXV0byB1IDogR1tub2RlXSkgewogICAgICAgIGlmICh1ICE9IHBhcmVudCkgewogICAgICAgICAgICBkZnModSwgbm9kZSwgdXNlZCwgRywgYSk7CiAgICAgICAgICAgIHN1bV9ub3RfY2hvc2VuICs9IG1heChkcFt1XVsxXSwgZHBbdV1bMF0pOwogICAgICAgICAgICBzdW1fY2hvc2VuICs9IG1heChkcFt1XVsxXSAtIDIgKiBkLCBkcFt1XVswXSk7CiAgICAgICAgfQogICAgfQogICAKICAgIGRwW25vZGVdWzFdID0gc3VtX2Nob3NlbjsgCQogICAgZHBbbm9kZV1bMF0gPSBzdW1fbm90X2Nob3NlbjsJCn0KCmludCBtYWluKCl7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKG51bGxwdHIpOwogICAgY291dC50aWUobnVsbHB0cik7CgogICAgbGwgdDsKICAgIGlmIChjaW4gPj4gdCkgewogICAgICAgIHdoaWxlICh0LS0pIHsKICAgICAgICAgICAgY2luID4+IG4gPj4gZDsKICAgICAgICAgICAgCiAgICAgICAgICAgIHZlY3RvcjxsbD4gYShuICsgMSwgMCk7IAogICAgICAgICAgICBmb3IgKGxsIGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgICAgICAgICAgY2luID4+IGFbaV07CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIHZlY3Rvcjx2ZWN0b3I8bGw+PiBHKG4gKyAxKTsgCiAgICAgICAgICAgIGZvciAobGwgaSA9IDE7IGkgPD0gbiAtIDE7IGkrKykgewogICAgICAgICAgICAgICAgbGwgdSwgdjsKICAgICAgICAgICAgICAgIGNpbiA+PiB1ID4+IHY7IAogICAgICAgICAgICAgICAgR1t1XS5wdXNoX2JhY2sodik7CiAgICAgICAgICAgICAgICBHW3ZdLnB1c2hfYmFjayh1KTsgCiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGRwLmFzc2lnbihuICsgNSwgdmVjdG9yPGxsPigyLCAwKSk7CiAgICAgICAgICAgIHZlY3RvcjxsbD4gdXNlZChuICsgMSwgMCk7IAoKICAgICAgICAgICAgZGZzKDEsIDAsIHVzZWQsIEcsIGEpOwogICAgICAgICAgICAKICAgICAgICAgICAgY291dCA8PCBtYXgoZHBbMV1bMV0sIGRwWzFdWzBdKSA8PCAiXG4iOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9

NQozIDEKMiAzIDEKMSAyCjIgMwozIDEKMyA2IDMKMSAyCjIgMwozIDEKLTIgLTMgLTEKMSAyCjIgMwo2IDEKNSAtNCAzIDYgNyAzCjQgMQo1IDEKMyA1CjMgNgoxIDIKOCAxCjMgNSAyIDcgOCA1IC0zIC00CjcgMwoxIDgKNCAzCjMgNQo3IDYKOCA3CjIgMQo=

5
3 1
2 3 1
1 2
2 3
3 1
3 6 3
1 2
2 3
3 1
-2 -3 -1
1 2
2 3
6 1
5 -4 3 6 7 3
4 1
5 1
3 5
3 6
1 2
8 1
3 5 2 7 8 5 -3 -4
7 3
1 8
4 3
3 5
7 6
8 7
2 1