#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(a) a.begin(),a.end()
typedef pair<int,int> PII;
typedef long long LL;
const int N = 2e5 + 10;
const int mod = 998244353;
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
int dx[8] = { 1,0,0,-1,-1,-1,1,1 };
int dy[8] = { 0,-1,1,0,-1,1,-1,1};
inline int gcd(int a, int b)
{
   if (b) while ((a %= b) && (b %= a));
   return a + b;
}
void solve()
{
    int n;
    cin >> n;
    vector<int>a(n + 1);
    vector<vector<int>>g(n + 1);
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int minpart = 0,root = 0;
    vector<int>sz(n + 1),buc(n + 1),dep(n + 1),mi(n + 1),mx(n + 1);
    for(int i = 1;i <= n;i++){
        mi[i] = mx[i] = a[i];
    }
    vector<bool>vis(n + 1);
    int tol = 0;
    auto getroot = [&](auto getroot,int sum,int u,int fa) -> void { 
        sz[u] = 1;
        int maxpart = 0;
        for(int v : g[u]){
            if(v == fa || vis[v]) continue;
            getroot(getroot,sum,v,u);
            sz[u] += sz[v];
            maxpart = max(maxpart,sz[v]);
        }
        maxpart = max(maxpart,sum - sz[u]);
        if(maxpart < minpart){
            minpart = maxpart;
            root = u;
        }
    };
    auto dfs = [&](auto dfs,int u,int fa) -> void {
        buc[++tol] = u;
        dep[u] = dep[fa] + 1;
        mx[u] = max(mx[fa],mx[u]);
        mi[u] = min(mi[fa],mi[u]);
        for(int v : g[u]){
            if(v == fa || vis[v]) continue;
            dfs(dfs,v,u);
        }
    };
    int ans = 1e18;
    auto sol = [&](auto sol,int sum,int u,int fa) -> void {
        minpart = sum;
        getroot(getroot,sum,u,fa);
        vis[root] = 1;
        dep[root] = 1;
        mi[root] = a[root];
        int res = 1e18;
        for(int v : g[root]){
            if(v == fa || vis[v]) continue;
            tol = 0;
            dfs(dfs,v,root);
            for(int i = 1;i <= tol;i++){
                int u = buc[i];
                ans = min({ans,mi[u] + dep[u] - max(mx[u],a[root]),mi[u] + dep[u] + res});
            }
            for(int i = 1;i <= tol;i++){
                int u = buc[i];
                res = min(res,dep[u] - 1 + mx[u]);
            }
        }
        for(auto v : g[root]){
            if(v == fa || vis[v]) continue;
            sol(sol,sz[v],v,root);
        }
    };
    sol(sol,n,1,0);
    cout << ans << endl;
}
signed main()
{
    io;
    int tt;
    cin >> tt;
    while(tt--){
        solve();
    }
	return 0;
}
/*

*/