#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;
    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[i].clear();
        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;
            std::vector<int> 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);
                }
            }
            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]);
            // std::cerr << i << " " << sta[0] << " " << std::min(f[sta[0]], qmin(i - dep[sta[0]], i - 1)) << std::endl;
            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++) tree[i].clear();
    }
    return 0;
}