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

#define ll long long
#define endl '\n'

const int maxn = 1e5 + 10;

int n;
ll a[maxn];
vector<int>t[maxn];
vector<int> g[maxn];

int dep[maxn], totdfn, dfn[maxn], f[maxn][20];

ll dp[maxn];

struct Node {
    int id, dep, dfn;
} node[maxn];



void dfs0 (int x, int fa) {
    dfn[x] = ++ totdfn;
    dep[x] = dep[fa] + 1;
    node[x].id = x; node[x].dfn = dfn[x]; node[x].dep = dep[x];
    f[x][0] = fa;
    for (int i = 1; i < 20; i ++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }

    for (auto y: t[x]) {
        if (y == fa) continue;
        dfs0(y, x);
    }
}

int lca(int x, int y) {
    while (dep[x] > dep[y]) {
        for (int i = 19; i >= 0; i --) {
            if (dep[f[x][i]] >= dep[y]) x = f[x][i];
        }
    }
    while (dep[y] > dep[x]) {
        for (int i = 19; i > 0; i --) {
            if (dep[f[y][i]] >= dep[x]) y = f[y][i];
        }
    }
    if (x == y) return x;
    for (int i = 19; i > 0; i --) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

ll mi[maxn][20], lg[maxn];
void pre () {
    lg[1] = 0;
    lg[2] = 1;
    for (int i = 3; i <= n; i ++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 0; i < n; i ++) mi[i][0] = a[i];
    for (int j = 1; j < 20; j ++) {
        for (int i = 0; i + (1 << (j - 1)) < n; i ++) {
            mi[i][j] = min (mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
        }
    }
}

ll getmina(int l, int r) {
    int s = lg[r - l + 1];
    return min (mi[l][s], mi[r - (1 << s) + 1][s]);
}

void dfs(int x, int fa, int d) {
    ll sum = 0;
    for (auto y: g[x]) {
        dfs(y, x, d);
        sum += dp[x];
    }
    if (sum == 0) sum = a[0];
    dp[x] = min (sum, getmina(d - dep[x], d - dep[fa]));
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    pre();

    for (int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    totdfn = 0;
    dfs0(1, 0);
    sort(node + 1, node + 1 + n, [&](Node x, Node y){
        if (x.dep == y.dep) return x.dfn < y.dfn;
        return x. dep < y.dep;
    });
    int now = 1, tmp = 1;
    vector<int> vt;
    ll ans = 0;
    while (now <= n) {
        vt.push_back(1);
        vector<int> vec;
        while (now <= n && tmp == node[now].dep) {
            vt.push_back(node[now].id);
            now ++;
        }
        vec = vt;
        sort(vt.begin(), vt.end(), [&](int x, int y){return dfn[x] < dfn[y];});
        for (int i = 1; i < vt.size() - 1; i ++) {
            int u = vt[i], v = vt[i + 1];
            int _lca = lca(u, v);
            vec.push_back(_lca);
        }
        sort(vec.begin(), vec.end(), [&](int x,int y){return dfn[x] < dfn[y];});
        int len = unique(vec.begin(), vec.end()) - vec.begin();
        vt.clear();
        for (int i = 1; i < len; i ++) {
            int u = vec[i - 1], v = vec[i];
            int _lca = lca(u, v);
            vt.push_back(_lca);
            g[_lca].push_back(v);
        }
        dfs(1, 0, tmp);
        ans += dp[1];
        tmp ++;
        for (auto x: vt) {
            g[x].clear();
        }
        vt.clear();
    }
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_ --) {
        solve();
    }

    return 0;
}

/*
3
3
1 2 3
3
1 1 1
5
1 2323 534 534 5
*/