#include <bits/stdc++.h>


void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;

int t;
int n, tot;
long long ans;

int a[N];

vector< int> G[N], E[N], D[N];

int Log[N];

void init( int n) {
    ans = tot = Log[1] = 0;

    for ( int i = 2; i <= n; i ++)
        Log[i] = Log[i >> 1] + 1;

    for ( int i = 1; i <= n; i ++)
        G[i].clear(), D[i].clear();
}

struct S_T {
    int f[N][18];

    void init_mi( int n, int a[]) {
        for ( int i = 1; i <= n; i ++) f[i][0] = a[i];
        
        for ( int j = 1; j <= Log[n]; j ++) 
            for ( int i = 1; i + (1 << j) - 1 <= n; i ++)
                f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }

    int ask_mi( int l, int r) {
        int s = Log[r - l + 1];
        return min(f[l][s], f[r - (1 << s) + 1][s]);
    }
} st;

int fa[N], siz[N], dep[N], son[N];
int top[N], dfn[N], vis[N];

long long dp[N];

int lxr[3 * N], len;

int cmp( int a, int b) {
    return dfn[a] < dfn[b];
}

void dfs1( int u, int fu) {
    fa[u] = fu, siz[u] = 1, dep[u] = dep[fu] + 1, son[u] = 0;
    D[dep[u]].push_back(u);

    for ( auto v : G[u]) {
        if (v == fu) continue ;

        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs2( int u, int topt) {
    top[u] = topt, dfn[u] = ++ tot;

    if (son[u]) dfs2(son[u], topt);

    for ( auto v : G[u])
        if (v != fa[u] && v != son[u]) dfs2(v, v);
}

int lca( int u, int v) {
    int tu = top[u], tv = top[v];

    while (tu != tv) {
        if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv);

        u = fa[tu], tu = top[u];
    }

    return dep[u] < dep[v] ? u : v;
}

void build( const vector< int> & vec, int D) {
    // cerr << "D: " << D << '\n';

    int len = 0, k = vec.size();
    for ( int i = 1; i <= k; i ++)
        lxr[++ len] = vec[i - 1], vis[vec[i - 1]] = 1;

    sort(lxr + 1, lxr + len + 1, cmp), len = unique(lxr + 1, lxr + len + 1) - lxr - 1;

    for ( int i = 1; i < k; i ++) lxr[++ len] = lca(lxr[i], lxr[i + 1]);

    lxr[++ len] = 1;
    sort(lxr + 1, lxr + len + 1, cmp), len = unique(lxr + 1, lxr + len + 1) - lxr - 1;

    for ( int i = 1; i < len; i ++) {
        int u = lca(lxr[i], lxr[i + 1]);
        E[u].push_back(lxr[i + 1]);

        // cerr << u << " " << lxr[i + 1] << '\n';
    }

    function< void( int)> dfs = [&]( int u) {
        dp[u] = vis[u] * a[1];
        int res = inf;

        for ( auto v : E[u]) {
            dfs(v);
            dp[u] += dp[v];
            res = min(res, st.ask_mi(D - dep[fa[v]] + 1, D - dep[u] + 1));
        }

        dp[u] = min(dp[u], 1ll * res);
    } ;

    dfs(1);
    for ( int i = 1; i <= len; i ++)
        E[lxr[i]].clear(), vis[lxr[i]] = 0;

    ans += dp[1];
    // cerr << dp[1] << '\n';
}

void solve() {
    cin >> n;
    init(n);

    for ( int i = 1; i <= n; i ++) cin >> a[i];

    for ( int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }

    st.init_mi(n, a);
    dfs1(1, 0), dfs2(1, 1);
    
    for ( int i = 1; i <= n; i ++) {
        if (! D[i].size()) continue ;

        build(D[i], i);
    }

    cout << ans << '\n';
    // cerr << "ANs: " << ans << '\n';
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> t;
    while (t --) solve();
    
    return 0;
}