#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
#define int long long
const int N=1e6+5;
int a[N];
vector<int>g[N];
bool del[N];
int sz[N], mxs[N];
int ans = 1e18;
void solve(int u, int siz){
    int root = -1, ms = siz+1;
    function<void(int,int)> dfs1 = [&](int u,int fa){//找到重心
        sz[u] = 1; mxs[u] = 0;
        for(auto v:g[u]) if(v!=fa && !del[v]){
            dfs1(v, u);
            sz[u] += sz[v];
            mxs[u] = max(mxs[u], sz[v]);
        }
        mxs[u] = max(mxs[u], siz-sz[u]);
        if(mxs[u] < ms) ms = mxs[u], root = u;
    };  
    dfs1(u, -1);
    int lstmi = 1e16, lstmx = 1e16;
    int lstmi2 = 1e16, lstmx2 = 1e16;
    for(auto v: g[root]) if(!del[v]){
        int nowmi = 1e16, nowmx = 1e16;
        int nowmi2 = 1e16, nowmx2 = 1e16;
        function<void(int,int,int,int,int)> dfs2 = [&](int u, int fa, int dep, int mi, int mx){
            sz[u] = 1;
            nowmi = min(nowmi, dep + mi);
            nowmi2 = min(nowmi2, dep + 1 + min(mi, a[root]));
            nowmx = min(nowmx, dep - mx);
            nowmx2 = min(nowmx2, dep + 1 - max(mx, a[root]));
            ans = min(ans, dep + 1 - max(mx, a[root]) + min(mi, a[root]));
            // ans = min(ans, lstmi + dep + 1 - max(mx, a[root]));
            // ans = min(ans, lstmx + dep + 1 + min(mi, a[root]));
            for(auto v: g[u]) if(v!=fa && !del[v]){
                dfs2(v, u, dep+1, min(mi, a[v]), max(mx, a[v]));
                sz[u]+=sz[v];
            }
        };
        dfs2(v, root, 1, a[v], a[v]);
        ans = min({ans, lstmi + nowmx2, lstmi2 + nowmx, 
                    lstmx + nowmi2, lstmx2 + nowmi});
        lstmi = min(lstmi, nowmi);
        lstmi2 = min(lstmi2, nowmi2);
        lstmx = min(lstmx, nowmx);
        lstmx2 = min(lstmx2, nowmx2);
    }
    del[root] = 1;
    for(auto v: g[root]) if(!del[v]){
        solve(v, sz[v]);
    }
}

void solve(){
    ans = 1e18;
    int n; cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        g[i].clear();
        del[i] = 0;
    }
    for(int i=1; i<n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    solve(1, n);
    ans = min(ans, 1ll);
    cout << ans << endl;

}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int T; T=1;
    cin >> T;
    while(T--) solve();
    return 0;
}