#include <algorithm>
#include <bit>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
void upd_min(int &a, int b) { if (a > b) a = b; }
constexpr int N = 1E6;
constexpr int inf = std::numeric_limits<int>::max();
int a[N + 1];
int DFN[N + 1];
int size[N + 1];
int b[N + 1];
constexpr int N_ = 2 * std::bit_ceil(static_cast<unsigned>(N));
int seg[N_], tag[N_];
int g_l, g_r;
int g_v;
void build(int u, int l, int r)
{
    tag[u] = 0;
    if (l == r - 1)
    {
        seg[u] = b[l];
        return;
    }
    int m = (l + r) / 2;
    build(u << 1, l, m);
    build(u << 1 | 1, m, r);
    seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]);
}
void modify(int u, int l, int r)
{
    if (g_l <= l && r <= g_r)
    {
        seg[u] += g_v;
        tag[u] += g_v;
        return;
    }
    int m = (l + r) / 2;
    if (g_l < m)
        modify(u << 1, l, m);
    if (m < g_r)
        modify(u << 1 | 1, m, r);
    seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]) + tag[u];
}
void solve()
{
    int n; std::cin >> n;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    std::vector<std::vector<int>> e(n + 1);
    auto add_edge = [&e](int u, int v) {
        e[u].push_back(v);
    };
    for (int i = n; --i; )
    {
        int ui, vi; std::cin >> ui >> vi;
        add_edge(ui, vi);
        add_edge(vi, ui);
    }
    int cnt = 0;
    std::function<void (int, int, int)> DFS = [&](int u, int t, int d) {
        ++cnt;
        DFN[u] = cnt;
        size[u] = 1;
        b[cnt] = d - a[u];
        for (int v : e[u])
            if (v != t)
                DFS(v, u, d + 1), size[u] += size[v];
    };
    DFS(1, 0, 1);
    build(1, 1, n + 1);
    int ans = inf;
    auto modify = [&](int l, int r, int v) {
        g_l = l, g_r = r, g_v = v;
        ::modify(1, 1, n + 1);
    };
    std::function<void (int, int)> DFS_ = [&](int u, int t) {
        upd_min(ans, a[u] + seg[1]);
        for (int v : e[u])
            if (v != t)
            {
                modify(1, n + 1, 1);
                modify(DFN[v], DFN[v] + size[v], -2);
                DFS_(v, u);
                modify(1, n + 1, -1);
                modify(DFN[v], DFN[v] + size[v], 2);
            }
    };
    DFS_(1, 0);
    std::cout << ans << "\n";
}
int main()
{
    std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);
    int T; std::cin >> T;
    while (T--) solve();
}