#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;
const int maxn = 1e6 + 5;
vector<int> g[maxn];
int a[maxn];
int ans;
bool v[maxn];

int get_size(int u, int fa){
    if (v[u]) return 0;
    int ans = 1;
    for(auto j : g[u]){
        if (j == fa) continue;
        ans += get_size(j, u);
    }
    return ans;
}

int get_wc(int u, int fa, int tot, int &wc){
    if (v[u]) return 0;
    int sum = 1, mx = 0;
    for(auto j : g[u]){
        if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        mx = max(mx, t);
        sum += t;
    }
    mx = max(mx, tot - sum);
    if (2 * mx <= tot){
        wc = u;
    }
    return sum;
}

void dfs(int u, int fa, int dep, int mn, int mx, vector<array<int, 3> > &p){
    if (v[u]) return;
    dep += 1;
    mn = min(mn, a[u]);
    mx = max(mx, a[u]);
    ans = min(ans, dep - mx + mn);
    p.push_back({dep, mn, mx});
    for(auto j : g[u]){
        if (j == fa or v[j]) continue;
        dfs(j, u, dep, mn, mx, p);
    }
}

void calc(int u){
    if (v[u]) return;
    get_wc(u, -1, get_size(u, -1), u);
    v[u] = true;
    int mn1 = 1e9, mn2 = 1e9;
    for(auto j : g[u]){
        if (v[j]) continue;
        vector<array<int, 3> > p;
        dfs(j, u, 1, a[u], a[u], p);
        for(auto [dep, mn, mx] : p){
            ans = min(ans, mn1 + dep + mn);
            ans = min(ans, mn2 + dep - mx);
        }
        for(auto [dep, mn, mx] : p){
            mn1 = min(mn1, dep - 1 - mx);
            mn2 = min(mn2, dep - 1 + mn);
        }
    }
    for(auto j : g[u]){
        calc(j);
    }
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            g[i].clear();
            v[i] = false;
        }
        ans = 1;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 0; i < n - 1; i++){
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        calc(1);
        cout << ans << '\n';
    }

}