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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto& i : a) cin >> i;
        vector<vector<int>> g(n);
        for (int i = 0; i < n -1 ; ++i) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> sz(n);
        vector<bool> del(n);
        auto sizes = [&](auto sizes, int u, int p) -> int {
            sz[u] = 1;
            for (auto to : g[u]) {
                if (del[to] || to == p) continue;
                sz[u] += sizes(sizes, to, u);
            }
            return sz[u];
        };
        int ans = 2;
        auto solve = [&](auto solve, int u) -> void {
            n = sizes(sizes, u, -1);
            while (true) {
                bool fnd = false;
                for (auto to : g[u]) {
                    if (sz[to] < sz[u] && sz[to] > n / 2) {
                        u = to;
                        fnd = true;
                        break;
                    }
                }
                if (!fnd) break;
            }
            vector<int> cur(4, 1e9);
            vector<int> tmp(4, 1e9);
            auto dfs = [&](auto dfs, int u, int p, int mx, int mn, int len) -> void {
                len++;
                mx = max(mx, a[u]);
                mn = min(mn, a[u]);
                tmp[0] = min(tmp[0], len);
                tmp[1] = min(tmp[1], len - mx);
                tmp[2] = min(tmp[2], len + mn);
                tmp[3] = min(tmp[3], len + mn - mx);
                for (auto to : g[u]) {
                    if (to == p || del[to]) continue;
                    dfs(dfs, to, u, mn, mx, len);
                }
            };
            cur[0] = cur[3] = 0;
            cur[1] = -a[u];
            cur[2] = a[u];
            for (auto to : g[u]) {
                if (del[to]) continue;
                fill(tmp.begin(), tmp.end(), 1e9);
                dfs(dfs, to, u, a[u], a[u], 1);
                for (int j = 0; j < 4; ++j) {
                    ans = min(ans, cur[3 ^ j] + tmp[j]);
                }
                for (int j = 0; j < 4; ++j) {
                    cur[j] = min(cur[j], tmp[j]);
                }
            }
            del[u] = true;
            for (auto to : g[u]) {
                if (!del[to]) solve(solve, to);
            }
        };
        solve(solve, 0);
        cout << ans << '\n';
    }
}