#include <bits/stdc++.h>
using namespace std;

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

#define PASSED debug("PASSED (%s) LINE #%s", __FUNCTION__, __LINE__)

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (x > y) x = y; }

const int N = 1e5 + 10;
int n, a[N], dfn[N], cnt, len[N], son[N], dep[N], lg2[N], st[18][N];
i64 f[N], g[N];
vector<int> G[N];

void dfs1(int x, int fa) {
    len[x] = 1, son[x] = 0;
    for (int y : G[x]) if (y != fa) {
        dep[y] = dep[x] + 1;
        dfs1(y, x);
        chkmax(len[x], len[y] + 1);
        if (!son[x] || len[son[x]] < len[y])
            son[x] = y;        
    }
}

void init_st() {
    for (int i = 0; i < n; i ++)
        st[0][i] = a[i];
    for (int i = 1; i < 18; i ++)
        for (int j = 0; j + (1 << i) - 1 < n; j ++)
            st[i][j] = st[i - 1][j], chkmin(st[i][j], st[i - 1][j + (1 << (i - 1))]);
}

i64 query_st(int l, int r) {
    if (l > r)
        return 1e18;
    int k = lg2[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

void dfs2(int x, int fa) {
    dfn[x] = ++ cnt;
    if (son[x])
        dfs2(son[x], x);
    for (int y : G[x]) if (y != fa && y != son[x])
        dfs2(y, x);
}

void dp(int x, int fa) {
    for (int y : G[x]) if (y != fa)
        dp(y, x);

    f[dfn[x]] = a[0], g[dfn[x]] = 0;
    for (int y : G[x]) if (y != fa && y != son[x]) {
        for (int i = 1; i <= len[y]; i ++) {
            if (g[dfn[x] + i] < i) {
                chkmin(f[dfn[x] + i], query_st(g[dfn[x] + i] + 1, i));
                g[dfn[x] + i] = i;
            }
            f[dfn[x] + i] += min(f[dfn[y] + i - 1], query_st(g[dfn[y] + i - 1], i - 1));
        }
    }
}

void solve() {
	cin >> n;
    cnt = 0;
    for (int i = 1; i <= n; i ++) {
        G[i].clear();
        g[i] = 0, f[i] = 1e18;
    }
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    for (int i = 2, x, y; i <= n; i ++) {
        cin >> x >> y;
        G[x].push_back(y), G[y].push_back(x);
    }
    dep[1] = 1;
    dfs1(1, 0);
    dfs2(1, 0);
    init_st();
    dp(1, 0);
    i64 ans = 0;
    for (int i = 1; i <= len[1]; i ++) {
        ans += min(f[i], query_st(g[i], i - 1));
    }
    cout << ans << "\n";
}

signed main() {
    for (int i = 2; i < N; i ++) {
        lg2[i] = lg2[i / 2] + 1;
    }
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
    while (tt --)
        solve();
	return 0;
}