#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }   
    std::vector<std::vector<int>> G(n);
    for (int i = 0; i < n - 1; i ++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    std::vector dp(n, std::vector<i64>(2, 0));
    auto dfs = [&](auto self, int u, int fa) -> void {
        for (int v: G[u]) {
            if (v == fa) continue;
            self(self, v, u);
            int mn = 2e9;
            dp[u][1] += std::min(dp[v][1], dp[v][0]);
            dp[u][0] += dp[v][1];
        }
        dp[u][1] += a[u];
    };
    dfs(dfs, 0, -1);
    int ans = std::min(dp[0][1], dp[0][0]);
    if (n == 1) ans = dp[0][1];
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false); 
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t --)
        solve();
    return 0;
}