#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...)
#endif
using namespace std;
#define ll long long
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) (void)(cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl)
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
struct edge {
    int v, w;
};
struct HLD {
    int n;
    vector<int> siz, top, parent, l, r, hson, dep;
    vector<vector<edge>> adj;
    int idx;
    vector<int> mn;  // 1-u的最小边权

    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n + 1), hson.resize(n + 1), top.resize(n + 1);
        parent.resize(n + 1);
        l.resize(n + 1), r.resize(n + 1);
        idx = 0;
        adj.resize(n + 1), dep.resize(n + 1);
        // 根据题目要求加数据结构
    }
    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
    }
    void work(int root = 1) {
        top[root] = root;
        parent[root] = -1;
        dep[root] = 1;
        dfs1(root, -1);
        dfs2(root, root);
    }
    void dfs1(int u, int f) {  // 搞fa,dep,son
        siz[u] = 1;
        for (auto [v, w] : adj[u]) {
            if (v == f)
                continue;
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[hson[u]] < siz[v])
                hson[u] = v;
        }
    }
    void dfs2(int u, int t) {  // 搞top
        top[u] = t;            // 记录链头
        l[u] = ++idx;
        if (!hson[u]) {
            r[u] = idx;
            return;
        }  // 无重儿子
        dfs2(hson[u], t);  // 搜重儿子
        for (auto [v, w] : adj[u]) {
            if (v == parent[u] || v == hson[u])
                continue;
            dfs2(v, v);  // 搜轻儿子
        }
        r[u] = idx;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    bool isAncester(int u, int v) {  // 判断u是不是v的祖先
        return l[u] <= l[v] && r[v] <= r[u];
    }
};
template <typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
    int n;
    vector<vector<T>> st;
    F func;

    SparseTable(const vector<T>& a, const F& f) : func(f) {
        n = (int)a.size() - 1;
        int max_log = __lg(n) + 1;
        st.resize(max_log + 1);
        st[0] = a;
        for (int j = 1; j <= max_log; j++) {
            st[j].resize(n + 1);
            for (int i = 1; i + (1 << (j - 1)) <= n; i++) {
                st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    T get(int l, int r) const {
        int len = __lg(r - l + 1);
        return func(st[len][l], st[len][r - (1 << len) + 1]);
    }
};
void solve() {
    int n;
    cin >> n;
    HLD hld(n);
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++) cin >> a[i];
    SparseTable<int> qmn(a, [](int i, int j) {
        return min(i, j);
    });
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        hld.addEdge(u, v, 1);
        hld.addEdge(v, u, 1);
    }
    auto cmp = [&](int i, int j) {
        return hld.l[i] < hld.l[j];
    };
    hld.work(1);
    auto buildvt = [&](vector<int>& node, vector<vector<edge>>& e, int rt) {
        node.push_back(rt);  // 保证根节点在虚树中存在
        sort(alls(node), cmp);
        node.erase(unique(alls(node)), node.end());
        set<int> tmp;
        for (auto x : node) tmp.insert(x);
        for (int i = 1; i < (int)node.size(); i++) tmp.insert(hld.lca(node[i - 1], node[i]));
        node.clear();
        for (auto x : tmp) node.push_back(x);
        sort(alls(node), cmp);
        vector<int> st;  // 维护一个栈
        for (auto v : node) {
            while (!st.empty() && !hld.isAncester(st.back(), v))
                st.pop_back();
            if (!st.empty())
                e[st.back()].push_back({v, hld.dep[v] - hld.dep[st.back()]});
            st.push_back(v);
        }
    };
    vector<vector<edge>> e(n + 1);
    vector<vector<int>> q(n + 1);
    int maxdep = 0;
    for (int i = 1; i <= n; i++) q[hld.dep[i]].push_back(i), maxdep = max(maxdep, hld.dep[i]);
    ll ans = 0;
    vector<ll> dp(n + 1, 1e18);
    int cur = 0;
    function<void(int, int)> cal = [&](int u, int fa) {
        ll tmp = 0;
        if (e[u].size() == 0)
            tmp = 1e18;
        for (auto [v, w] : e[u]) {
            if (v == fa)
                continue;
            deb(u, v);
            cal(v, u);
            int ql = cur - hld.dep[v];
            int qr = cur - hld.dep[u] - 1;
            assert(ql <= qr);
            ql++;
            qr++;  // 深度偏移
            tmp += min(dp[v], (ll)qmn.get(ql, qr));
        }
        dp[u] = min(tmp, (ll)a[cur - hld.dep[u] + 1]);  // +1是深度偏移
    };
    auto clear = [&](vector<int>& node) {
        for (auto x : node) {
            e[x].clear();
            dp[x] = 1e18;
        }
    };
    for (int i = 1; i <= maxdep; i++) {
        vector<int> node;
        for (auto x : q[i]) node.push_back(x);
        cur = i;
        deb(i, node);
        buildvt(node, e, 1);
        cal(1, 1);
        deb(dp[1]);
        ans += dp[1];
        clear(node);
        deb("end");
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef LOCAL
    double starttime = clock();
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    while (t--) solve();
#ifdef LOCAL
    double endtime = clock();
    cerr << "Time Used: " << (double)(endtime - starttime) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
    return 0;
}