#include<bits/stdc++.h>

using namespace std;

#define int long long
int const maxn = 1e5 + 5;
int a[maxn], cmp[maxn], inf = 1e18, h[maxn];
vector < int > g[maxn];
deque < pair < int, pair < int, int > > > dp[maxn];
int mn[(1 << 18)], n;

void build(int i, int l, int r) {
    if (r - l == 1) {
        mn[i] = a[l];
        return;
    }
    int m = (r + l) / 2;
    build(2 * i + 1, l, m);
    build(2 * i + 2, m, r);
    mn[i] = min(mn[2 * i + 1], mn[2 * i + 2]);
}

int get(int i, int l, int r, int lq, int rq) {
    if (lq >= r || l >= rq) return inf;
    if (lq <= l && r <= rq) return mn[i];
    int m = (r + l) / 2;
    return min(get(2 * i + 1, l, m, lq, rq), get(2 * i + 2, m, r, lq, rq));
}

void dfs(int v, int p) {
    h[v] = h[p] + 1;
    dp[v] = {}, cmp[v] = v;
    for (auto u : g[v]) {
        if (u != p) {
            dfs(u, v);
            if (dp[cmp[u]].size() > dp[cmp[v]].size()) cmp[v] = cmp[u];
        }
    }
    int R = 0;
    for (auto u : g[v]) {
        if (u == p || cmp[u] == cmp[v]) continue;
        R = max(R, (int)dp[cmp[u]].size());
    }
    if (p == 0) R = dp[cmp[v]].size();
    for (int i = 0; i < R; i++) {
        dp[cmp[v]][i].first = min(dp[cmp[v]][i].first, get(0, 0, n, dp[cmp[v]][i].second.first, dp[cmp[v]][i].second.first + dp[cmp[v]][i].second.second - h[v]));
    }
    for (auto u : g[v]) {
        if (u == p || cmp[u] == cmp[v]) continue;
        for (int mx = 0; mx < dp[cmp[u]].size(); mx++) {
            dp[cmp[v]][mx].first += min(dp[cmp[u]][mx].first, get(0, 0, n, dp[cmp[u]][mx].second.first, dp[cmp[u]][mx].second.first + dp[cmp[u]][mx].second.first - h[v]));
        }
    }
    dp[cmp[v]].push_front({a[0], {0, h[v]}});
    for (int i = 1; i <= R; i++) {
        dp[cmp[v]][i].first = min(dp[cmp[v]][i].first, a[i]);
        dp[cmp[v]][i].second = {i, h[v]};
    }
}

main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int u, v;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i - 1];
            g[i] = {};
        }
        build(0, 0, n);
        for (int i = 1; i < n; i++) {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        int ans = 0;
        for (auto key : dp[cmp[1]]) {
            ans += key.first;
        }
        cout << ans << '\n';
    }
    return 0;
}