#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 (2, std::vector<i64>(2)));
    auto dfs = [&](auto self, int u, int fa) -> void {
        if (u == 0 && G[u].size() == 0 || u != 0 && G[u].size() == 1) {
            dp[u][0][0] = 0;
            dp[u][1][1] = a[u];
            dp[u][0][1] = 1e18;
            return ;
        }
        int ok = 0;
        for (int v: G[u]) {
            if (v == fa) continue;
            self(self, v, u);
            dp[u][1][1] += std::min({dp[v][0][1], dp[v][0][0], dp[v][0][1]});
            if (dp[v][0][1] >= dp[v][1][1]) {
                ok = 1;
                dp[u][0][1] += dp[v][1][1];
            } else {
                dp[u][0][1] += dp[v][0][1];
            }
            dp[u][0][0] += dp[v][0][1];
        }
        int s = dp[u][0][1];
        if (!ok) {
            for (int v: G[u]) {
                if (v == fa) continue;
                dp[u][0][1] = std::min(dp[u][0][1], s - dp[v][0][1] + dp[v][1][1]);
            }
        }

        dp[u][1][1] += a[u];
    };
    dfs(dfs, 0, -1);
    std::cout << std::min(dp[0][1][1], dp[0][0][1]) << "\n";
}

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