#include <bits/stdc++.h>

using LL = long long;

constexpr int inf32 = (int)(1e9) + 9;
constexpr int N = 100005;

int n, a[N], b[20][N];
std::vector<int> tree[N], tree1[N];
int dep[N], fa[20][N], dfc, dfn[N];
void predfs(int u, int p) {
    dfn[u] = ++dfc;
    dep[u] = dep[p] + 1;
    fa[0][u] = p;
    for (int i = 1; i < 20; i++) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (int v : tree[u]) if (v != p) predfs(v, u);
}
int lca(int x, int y) {
    if (dep[x] > dep[y]) std::swap(x, y);
    for (int i = 19; i >= 0; i--) if (dep[fa[i][y]] >= dep[x]) y = fa[i][y];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) if (fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}
std::vector<int> h[N];
int f[N];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    bool tag = T < 10;
    while (T--) {
        std::cin >> n;
        for (int i = 0; i < n; i++) std::cin >> a[i];
        for (int i = 1; i < n; i++) {
            int x, y;
            std::cin >> x >> y;
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        for (int i = 0; i < n; i++) b[0][i] = a[i];
        for (int i = 1; i < 20; i++) for (int j = 0; j + (1 << i) - 1 < n; j++) b[i][j] = std::min(b[i - 1][j], b[i - 1][j + (1 << i - 1)]);
        const auto qmin = [&](int l, int r) {
            int k = std::__lg(r - l + 1);
            return std::min(b[k][l], b[k][r - (1 << k) + 1]);
        };
        LL ans = 0;
        dfc = 0;
        predfs(1, 0);
        for (int i = 1; i <= n; i++) h[dep[i]].push_back(i);
        for (int i = 1; i <= n; i++) {
            if (!h[i].size()) continue;
            std::sort(h[i].begin(), h[i].end(), [](int x, int y) { return dfn[x] < dfn[y]; });
            std::vector<int> clc, sta;
            const auto at = [&](int i) -> int& { return *((i >= 0 ? sta.begin() : sta.end()) + i); };
            for (int x : h[i]) {
                clc.push_back(x);
                if (!sta.size()) sta.push_back(x);
                else {
                    int p = lca(at(-1), x);
                    while (sta.size() > 1) {
                        if (dep[at(-2)] >= dep[p]) {
                            tree1[at(-2)].push_back(at(-1));
                            sta.pop_back();
                        }
                    }
                    if (at(-1) != p) {
                        // clc.push_back(p);
                        tree1[p].push_back(at(-1));
                        at(-1) = p;
                    }
                    sta.push_back(x);
                }
            }
            if (tag) {
                while (sta.size() > 1) {
                    tree1[at(-2)].push_back(at(-1));
                    sta.pop_back();
                }
                const std::function<void(int)> dfs = [&](int u) {
                    f[u] = a[i - dep[u]];
                    if (tree1[u].size()) {
                        int sum = 0;
                        for (int v : tree1[u]) {
                            dfs(v);
                            sum = std::min(inf32, sum + f[v]);
                        }
                        f[u] = std::min(f[u], sum);
                    }
                };
                dfs(sta[0]);
                ans += std::min(f[sta[0]], qmin(i - dep[sta[0]], i - 1));
            }
            for (int x : clc) tree1[x].clear();
        }
        std::cout << ans << "\n";
        for (int i = 1; i <= n; i++) h[i].clear();
        for (int i = 1; i <= n; i++) tree[i].clear();
    }
    return 0;
}