#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>(3));
    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;
            dp[u][1] = a[u];
            dp[u][2] = 1e18;
            return ;
        }
        int ok = 0;
        for (int v: G[u]) {
            if (v == fa) continue;
            self(self, v, u);
            dp[u][0] += dp[v][2];
            dp[u][1] += std::min({dp[v][0], dp[v][1], dp[v][2]});
            if (dp[v][2] >= dp[v][1]) {
                ok = 1;
                dp[u][2] += dp[v][1];
            } else {
                dp[u][2] += dp[v][2];
            }
        }
        if (!ok) {
            i64 mn = 1e18;
            for (int v: G[u]) {
                if (v == fa) continue;
                mn = std::min(mn, dp[u][2] - dp[v][2] + dp[v][1]);
            }
            dp[u][2] = mn;
        }
        dp[u][1] += a[u];
    };
    dfs(dfs, 0, -1);
    std::cout << std::min(dp[0][1], dp[0][2]) << "\n";
}

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