/**
 *    author:  longvu
 *    created: 09/22/24 22:35:37
**/
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
const int INF = 1e18;
const int nax = (int)(100001);
const int mod = 1e9 + 7;

template<class X, class Y>
bool maximize(X& x, const Y y) {
    if (y > x) {x = y; return true;}
    return false;
}
template<class X, class Y>
bool minimize(X& x, const Y y) {
    if (y < x) {x = y; return true;}
    return false;
}

#define Fi first
#define Se second

const int LOG = 18;

pair<int, int> rmq[nax][LOG + 1];
int euler[nax], h[nax], Log2[nax], fir[nax];
vector<int> adj[nax];
int m = 0;
void dfs(int u, int pa) {
    euler[++m] = u;
    fir[u] = m;
    rmq[m][0] = {h[euler[m]], euler[m]};
    for (auto v : adj[u]) {
        if (v == pa) {
            continue;
        }
        h[v] = 1 + h[u];
        dfs(v, u);
        euler[++m] = u;
        rmq[m][0] = {h[euler[m]], euler[m]};
    }
}

void precal() {
    m = 0;
    dfs(1, -1);
    for (int k = 1; k <= LOG; ++k) {
        for (int i = 1; i + (1 << k) - 1 <= m; ++i) {
            rmq[i][k] = min(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int find_lca(int u, int v) {
    int l = min(fir[u], fir[v]), r = max(fir[u], fir[v])
                                     , k = Log2[r - l + 1];
    return min(rmq[l][k], rmq[r - (1 << k) + 1][k]).Se;
}

int a[nax], dp[nax], rmqp[nax][LOG + 1];
vector<int> memo[nax];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 2; i < nax; ++i) {
        Log2[i] = 1 + Log2[i >> 1];
    }
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            rmqp[i][0] = a[i];
        }
        for (int k = 1; k <= LOG; ++k) {
            for (int i = 0; i + (1 << k) - 1 < n; ++i) {
                rmqp[i][k] = min(rmqp[i][k - 1], rmqp[i + (1 << (k - 1))][k - 1]);
            }
        }
        auto get = [&](int l, int r) {
            int k = Log2[r - l + 1];
            return min(rmqp[l][k], rmqp[r - (1 << k) + 1][k]);
        };
        for (int i = 0; i <= n; ++i) {
            adj[i].clear();
            memo[i] = { -1};
        }
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        precal();
        for (int i = 1; i <= n; ++i) {
            memo[h[i]].push_back(i);
        }
        int ans = 0;
        for (int hi = 0; hi < n; ++hi) {
            sort(1 + all(memo[hi]), [&](int u, int v) {
                return fir[u] < fir[v];
            });
            for (int i = 0; i < sz(memo[hi]); ++i) {
                dp[i] = INF;
            }
            dp[0] = 0;
            for (int i = 1; i < sz(memo[hi]); ++i) {
                if (sz(memo[hi]) == 1) {
                    continue;
                }
                int l = 1, r = i;
                auto cal = [&](int z) {
                    return get(hi - h[find_lca(memo[hi][z], memo[hi][i])], hi) + dp[z - 1];
                };
                while (r - l >= 1) {
                    int mid1 = (2 * l + r) / 3, mid2 = (l + 2 * r) / 3;
                    if (cal(mid1) >= cal(mid2)) {
                        l = mid1 + 1;
                    } else {
                        r = mid2 - 1;
                    }
                }
                l--;
                minimize(dp[i], cal(l));
                minimize(dp[i], cal(min(i, l + 1)));
                assert(dp[i - 1] <= dp[i]);
            }
            // cout << hi << " " << dp[sz(memo[hi]) - 1] << '\n';
            ans += dp[sz(memo[hi]) - 1];
        }
        cout << ans << '\n';
    }
    return 0;
}