#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

inline int read() {
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int w[N];
ll f[N], g[N], h[N];
vector<int> G[N];

void dfs(int u, int fa) {
    f[u] = w[u], h[u] = 0;
    ll mn = 1e18;
    for (int v: G[u]) 
        if (v != fa) {
            dfs(v, u);
            f[u] += min(f[v], min(g[v], h[v]));
            h[u] += min(f[v], g[v]);
            mn = min(mn, max(0ll, f[v] - g[v]));
        }
    g[u] = h[u] + mn;
    // cout << u << ' ' << f[u] << ' ' << g[u] << ' ' << h[u] << el;
}

void solve() {
    int n = read();
    for (int i = 1; i <= n; ++i) w[i] = read(), G[i].clear();
    for (int i = 1; i < n; ++i) {
        int a = read(), b = read();
        G[a].emplace_back(b), G[b].emplace_back(a);
    }
    dfs(1, 0);
    cout << min(f[1], g[1]) << el;
}

int main() {
    // ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}