#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
const int maxN = 1e5 + 10;
int a[maxN];
vector<int> g[maxN];
ll dp[maxN][2][2];
ll ndp[2][2];
void dfs(int v, int p) {
    for (int x = 0; x < 2; x++) {
        for (int y = 0; y < 2; y++) {
            dp[v][x][y] = 1e18;
        }
    }
    dp[v][0][0] = 0;
    dp[v][1][1] = a[v];
    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                ndp[x][y] = 1e18;
            }
        }
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                for (int z = 0; z < 2; z++) {
                    for (int t = 0; t < 2; t++) {
                        int ny = y | z;
                        if (!x && !t) continue;
                        ndp[x][ny] = min(ndp[x][ny], dp[v][x][y] + dp[to][z][t]);
                    }
                }
            }
        }
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                dp[v][x][y] = ndp[x][y];
            }
        }
    }
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, -1);
    cout << min(dp[1][0][1], dp[1][1][1]) << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}