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

template <typename T>
class Segment_Tree {
    using F = std::function<T(T, T)>;

private:
    int N, le;
    T e;
    F f;
    std::vector<T> segment_tree;

public:
    Segment_Tree(int N, F f, T e, const std::vector<T>& lst = {})
        : N(N), f(f), e(e) {
        le = 1;
        while (le < N) le *= 2;
        segment_tree.assign(2 * le, e);
        if (!lst.empty()) {
            assert((int)lst.size() <= N);
            for (int i = 0; i < (int)lst.size(); ++i) {
                segment_tree[le + i] = lst[i];
            }
            for (int i = le - 1; i > 0; --i) {
                segment_tree[i] = f(segment_tree[2 * i], segment_tree[2 * i + 1]);
            }
        }
    }
    void Build(const std::vector<T>& lst) {
        // リストをセグメントツリーの葉に配置
        for (size_t i = 0; i < lst.size(); ++i) {
            segment_tree[le + i] = lst[i];
        }
        // 残りを初期値で埋める
        for (size_t i = lst.size(); i < le; ++i) {
            segment_tree[le + i] = e;
        }
        // 親ノードを構築
        for (int i = le - 1; i > 0; --i) {
            segment_tree[i] = f(segment_tree[2 * i], segment_tree[2 * i + 1]);
        }
    }

    T operator[](int i) const {
        if (i < 0) i += le;
        assert(0 <= i && i < le);
        return segment_tree[le + i];
    }

    void update(int i, T x) {
        if (i < 0) i += le;
        assert(0 <= i && i < le);
        i += le;
        segment_tree[i] = x;
        while (i > 1) {
            i /= 2;
            segment_tree[i] = f(segment_tree[2 * i], segment_tree[2 * i + 1]);
        }
    }

    T Fold(int L, int R) const {
        T vL = e, vR = e;
        for (L += le, R += le; L < R; L /= 2, R /= 2) {
            if (L & 1) vL = f(vL, segment_tree[L++]);
            if (R & 1) vR = f(segment_tree[--R], vR);
        }
        return f(vL, vR);
    }
};

#include <vector>
#include <functional>
#include <cassert>

template <typename T>
class Sparse_Table {
    using F = std::function<T(T, T)>;

private:
    int N, n;
    T e;
    F f;
    std::vector<std::vector<T>> dp;

public:
    Sparse_Table(int N, F f, T e, const std::vector<T>& lst)
        : N(N), f(f), e(e) {
        n = 0;
        while ((1 << n) <= N) ++n;
        dp.assign(n, std::vector<T>(N, e));
        if (!lst.empty()) {
            assert((int)lst.size() == N);
            for (int i = 0; i < N; ++i) {
                dp[0][i] = lst[i];
            }
            for (int j = 1; j < n; ++j) {
                for (int i = 0; i + (1 << j) <= N; ++i) {
                    dp[j][i] = f(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
                }
            }
        }
    }

    T Fold(int L, int R) const {
        if (L == R) return e;
        int k = 31 - __builtin_clz(R - L); // log2(R - L)
        return f(dp[k][L], dp[k][R - (1 << k)]);
    }
};

#include <vector>
#include <algorithm>
#include <functional>
#include <limits>
#include <stack>

using namespace std;

class Graph {
public:
    int V;
    bool directed, weighted;
    double inf;
    vector<vector<pair<int, int>>> graph;
    vector<int> lca_euler_tour, lca_parents, lca_dfs_in_index, lca_dfs_out_index;
    Segment_Tree<int> *ST;
    vector<bool> auxiliary_tree_use;

    Graph(int V, vector<tuple<int, int, int>> edges, bool directed = false, bool weighted = false, double inf = numeric_limits<double>::infinity())
        : V(V), directed(directed), weighted(weighted), inf(inf), graph(V) {
        for (auto &[u, v, d] : edges) {
            graph[u].emplace_back(v, d);
            if (!directed) {
                graph[v].emplace_back(u, d);
            }
        }
    }

    void Build_LCA(int root, bool segment_tree = false) {
        vector<int> depth(V, 0);
        auto [et, ps, d] = SIV_DFS(root);
        lca_euler_tour = et;
        lca_parents = ps;
        lca_dfs_in_index.resize(V, -1);
        lca_dfs_out_index.resize(V, -1);

        for (int i = 0; i < et.size(); ++i) {
            if (et[i] >= 0) {
                lca_dfs_in_index[et[i]] = i;
            } else {
                lca_dfs_out_index[~et[i]] = i;
            }
        }

        if (segment_tree) {
            vector<int> lst(et.size(), -1);
            for (int i = 0; i < et.size(); ++i) {
                if (et[i] >= 0) {
                    lst[i] = depth[et[i]];
                } else {
                    lst[i] = depth[lca_parents[~et[i]]];
                }
            }
            ST = new Segment_Tree<int>(et.size(), [](int a, int b) { return min(a, b); }, V);
            ST->Build(lst);
        }
    }

    int LCA(int a, int b) {
        if (lca_dfs_in_index[a] > lca_dfs_in_index[b]) swap(a, b);
        int m = lca_dfs_in_index[a], M = lca_dfs_in_index[b];
        return lca_euler_tour[ST->Fold(m, M + 1)];
    }

    void Build_Auxiliary_Tree(int root){
        Build_LCA(root,true);
        auxiliary_tree_use=vector<bool>(V, false);
    }

    pair<vector<int>, vector<int>> Auxiliary_Tree(vector<int> points) {
        for (int p : points) {
            auxiliary_tree_use[p] = true;
        }
        sort(points.begin(), points.end(), [&](int x, int y) {
            return lca_dfs_in_index[x] < lca_dfs_in_index[y];
        });

        for (size_t i = 0; i + 1 < points.size(); ++i) {
            int lca = LCA(points[i], points[i + 1]);
            if (!auxiliary_tree_use[lca]) {
                points.push_back(lca);
                auxiliary_tree_use[lca] = true;
            }
        }

        sort(points.begin(), points.end(), [&](int x, int y) {
            return lca_dfs_in_index[x] < lca_dfs_in_index[y];
        });

        vector<int> parents(points.size(), -1);
        vector<int> stack;
        for (size_t i = 0; i < points.size(); ++i) {
            while (!stack.empty() && lca_dfs_out_index[points[stack.back()]] < lca_dfs_in_index[points[i]]) {
                stack.pop_back();
            }
            if (!stack.empty()) {
                parents[i] = stack.back();
            }
            stack.push_back(i);
        }

        for (int p : points) {
            auxiliary_tree_use[p] = false;
        }

        return {parents, points};
    }

    tuple<vector<int>, vector<int>, vector<int>> SIV_DFS(int root) {
        vector<bool> seen(V, false), finished(V, false);
        vector<int> et, ps(V, -1), depth(V, 0);
        stack<int> st;
        st.push(root);

        while (!st.empty()) {
            int x = st.top();
            st.pop();
            if (!seen[x]) {
                seen[x] = true;
                et.push_back(x);
                for (auto &[y, d] : graph[x]) {
                    if (!seen[y]) {
                        st.push(y);
                        ps[y] = x;
                        depth[y] = depth[x] + 1;
                    }
                }
            } else if (!finished[x]) {
                finished[x] = true;
                et.push_back(~x);
            }
        }
        return {et, ps, depth};
    }
private:
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;

        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }

        const int inf = 1 << 30;
        Sparse_Table<int> ST(N, [](int a, int b) { return min(a, b); }, inf, A);

        vector<tuple<int,int,int>> edges(N);
        for (int m = 0; m < N - 1; ++m) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            edges.emplace_back(u,v,m);
        }

        Graph G(N, edges,false,true);
        G.Build_Auxiliary_Tree(0);

        vector<int> depth = get<2>(G.SIV_DFS(0));

        long long ans = 0;
        vector<vector<int>> idx(N);

        for (int x = 0; x < N; ++x) {
            idx[depth[x]].push_back(x);
        }

        for (int d = 0; d < N; ++d) {
            auto [parents, P] = G.Auxiliary_Tree(idx[d]);
            int le = parents.size();
            vector<int> cnt(le, 0);

            for (int p : parents) {
                if (p != -1) { // C++ではNoneの代わりに-1を使用
                    cnt[p]++;
                }
            }

            queue<int> q;
            for (int x = 0; x < le; ++x) {
                if (cnt[x] == 0) {
                    q.push(x);
                }
            }

            vector<int> dp(le, 0);
            while (!q.empty()) {
                int x = q.front();
                q.pop();

                if (depth[P[x]] == d) {
                    dp[x] = A[0];
                }
                dp[x] = min(dp[x], ST.Fold(d - depth[P[x]], d + 1));

                if (parents[x] != -1) {
                    dp[parents[x]] += dp[x];
                    cnt[parents[x]]--;
                    if (cnt[parents[x]] == 0) {
                        q.push(parents[x]);
                    }
                }
            }

            if (le) {
                auto it = find(parents.begin(), parents.end(), -1);
                if (it != parents.end()) {
                    ans += dp[it - parents.begin()];
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}