#include <algorithm>
#include <cstdint>
#include <ios>
#include <iostream>
#include <utility>
#include <vector>

namespace segment_tree {

    constexpr std::int32_t log_2(std::int32_t);

    template <typename P>
    std::int32_t for_lvls(std::int32_t node, std::int32_t sz, bool dir, P p) {

        while (node < sz) {
            node = (node << 1 | dir) + (!dir ? p(node) : -p(node));
        }

        return node;

    }

    template <typename F>
    void for_pars(std::int32_t node, bool dir, F f) {

        const std::int32_t lvls = log_2(node);

        for (std::int32_t i = 1; i <= lvls; ++i) {
            f(node >> (!dir ? lvls - i + 1 : i));
        }

    }

    template <typename F>
    void for_rng(std::int32_t node_l, std::int32_t node_r, F f) {

        while (node_l < node_r) {
            if (node_l & 1) {
                f(node_l);
                ++node_l;
            }
            if (node_r & 1) {
                --node_r;
                f(node_r);
            }
            node_l >>= 1;
            node_r >>= 1;
        }

    }

    template <typename F>
    void for_rng_ord(std::int32_t node_l, std::int32_t node_r, bool dir, F f) {

        std::int32_t base = !dir ? node_l - 1 : node_r;
        const std::int32_t mask = (1 << log_2((node_l - 1) ^ node_r)) - 1;
        const std::int32_t shft = !dir ? 1 : -1;

        std::int32_t node = (!dir ? -node_l : node_r) & mask;

        while (node) {
            const std::int32_t bit = __builtin_ctz(node);
            f((base >> bit) + shft);
            node ^= 1 << bit;
        }

        base = dir ? node_l - 1 : node_r;
        node = (dir ? -node_l : node_r) & mask;

        while (node) {
            const std::int32_t bit = log_2(node);
            f((base >> bit) - shft);
            node ^= 1 << bit;
        }

    }

    constexpr std::int32_t log_2(std::int32_t x) {

        return 31 - __builtin_clz(x);

    }

}

template <typename F>
class y_combinator {

private:

    F f;

public:

    explicit y_combinator(F&& f) : f(f) {}

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {

        return f(*this, std::forward<Args>(args)...);

    }

};

template <typename F>
y_combinator(F) -> y_combinator<F>;

void solve() {

    std::int32_t n;

    std::cin >> n;

    std::vector<std::int32_t> a(n);

    for (auto& x : a) {
        std::cin >> x;
    }

    std::vector<std::vector<std::int32_t>> adj(n);

    for (std::int32_t i = 0; i < n - 1; ++i) {
        std::int32_t u;
        std::int32_t v;
        std::cin >> u >> v;
        --u;
        --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<std::int32_t> deps(n);
    std::vector<std::int32_t> dfn(n);
    const std::int32_t lvls = 32 - __builtin_clz(n - 1);
    std::int64_t mn_cst = 0;
    const std::int64_t mx = std::int64_t(*std::max_element(std::begin(a), std::end(a))) * n;
    std::vector<std::vector<std::int32_t>> nodes(n);
    const std::int32_t seg_sz = 1 << segment_tree::log_2(n * 2 - 1);
    std::int32_t tm = 0;
    std::vector<std::vector<std::int32_t>> v_adj(n);

    std::vector ancs(lvls, std::vector(n, std::int32_t(-1)));
    std::vector<std::int64_t> dp(n, mx + 1);
    std::vector seg(seg_sz * 2, mx + 1);

    y_combinator(
        [&](auto self, std::int32_t node, std::int32_t par) -> void {
            ancs[0][node] = par;
            deps[node] = par != -1 ? deps[par] + 1 : 0;
            dfn[node] = tm;
            ++tm;
            nodes[deps[node]].push_back(node);
            for (auto x : adj[node]) {
                if (x != par) {
                    self(x, node);
                }
            }
        }
    )(0, -1);

    for (std::int32_t i = 1; i < lvls; ++i) {
        for (std::int32_t j = 0; j < n; ++j) {
            const std::int32_t anc = ancs[i - 1][j];
            ancs[i][j] = anc != -1 ? ancs[i - 1][anc] : -1;
        }
    }

    std::copy_n(std::begin(a), n, std::begin(seg) + seg_sz);

    for (std::int32_t i = seg_sz - 1; i; --i) {
        seg[i] = std::min(seg[i << 1], seg[i << 1 | 1]);
    }

    for (std::int32_t i = 0; i < n && !std::empty(nodes[i]); ++i) {
        std::vector<std::int32_t>& c_nodes = nodes[i];
        const auto cmp = [&](std::int32_t node_1, std::int32_t node_2) -> bool {
            return dfn[node_1] < dfn[node_2];
        };
        const auto lca = [&](std::int32_t node_1, std::int32_t node_2) -> std::int32_t {
            for (std::int32_t i = lvls - 1; i >= 0; --i) {
                if (deps[node_1] - deps[node_2] >= 1 << i) {
                    node_1 = ancs[i][node_1];
                }
                if (deps[node_2] - deps[node_1] >= 1 << i) {
                    node_2 = ancs[i][node_2];
                }
            }
            if (node_1 == node_2) {
                return node_1;
            }
            for (std::int32_t i = lvls - 1; i >= 0; --i) {
                if (ancs[i][node_1] != ancs[i][node_2]) {
                    node_1 = ancs[i][node_1];
                    node_2 = ancs[i][node_2];
                }
            }
            return ancs[0][node_1];
        };
        c_nodes.emplace_back();
        std::int32_t sz = std::size(c_nodes);
        c_nodes.reserve(sz * 2 - 1);
        std::sort(std::begin(c_nodes), std::end(c_nodes), cmp);
        for (std::int32_t j = 0; j < sz - 1; ++j) {
            c_nodes.push_back(lca(c_nodes[j], c_nodes[j + 1]));
        }
        std::sort(std::begin(c_nodes), std::end(c_nodes), cmp);
        c_nodes.erase(std::unique(std::begin(c_nodes), std::end(c_nodes)), std::end(c_nodes));
        sz = std::size(c_nodes);
        for (std::int32_t j = 1; j < sz; ++j) {
            v_adj[lca(c_nodes[j - 1], c_nodes[j])].push_back(c_nodes[j]);
        }
        for (std::int32_t j = sz - 1; j >= 0; --j) {
            const std::int32_t node = c_nodes[j];
            segment_tree::for_rng(
                seg_sz + i - deps[node], seg_sz + i + 1,
                [&](std::int32_t seg_node) -> void {
                    dp[node] = std::min(dp[node], seg[seg_node]);
                }
            );
            if (deps[node] != i) {
                std::int64_t cst = 0;
                for (auto x : v_adj[node]) {
                    cst += dp[x];
                }
                dp[node] = std::min(dp[node], cst);
            }
        }
        mn_cst += dp[0];
        for (auto x : c_nodes) {
            dp[x] = mx + 1;
            v_adj[x].clear();
        }
    }

    std::cout << mn_cst << '\n';

}

int main() {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    std::int32_t t;

    std::cin >> t;

    for (std::int32_t i = 0; i < t; ++i) {
        solve();
    }

    return 0;

}