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

const int N=1e6+5,inf=1e9;
int n,a[N],x,y;
vector<int> e[N];
void adde(int x,int y){
    e[x].push_back(y);
}
int rt,mw[N],all,sz[N];
bool vis[N];
void dfs1(int u,int f){
	sz[u]=1,mw[u]=0;
	for(int v:e[u])if(!vis[v]&&(v^f)){
		dfs1(v,u);
		sz[u]+=sz[v];
		mw[u]=max(mw[u],sz[v]);
	}
	mw[u]=max(mw[u],all-sz[u]);
	if(mw[u]<mw[rt])rt=u;
}
int ans;
void dfs3(int u,int f,int mx,int mn,int dis){
    ans=min(ans,dis-mx+mn);
    for(int v:e[u])if(!vis[v]&&(v^f))
        dfs3(v,u,max(mx,a[v]),min(mn,a[v]),dis+1);
}
int lstmx,lstmn;
int curmx,curmn;
void dfs4(int u,int f,int mx,int mn,int dis){
    curmx=min(curmx,dis-mx);
    curmn=min(curmn,dis+mn);
    for(int v:e[u])if(!vis[v]&&(v^f))
        dfs4(v,u,max(mx,a[v]),min(mn,a[v]),dis+1);
}
void dfs2(int u){
	vis[u]=1;
    dfs3(u,0,a[u],a[u],1);
    lstmx=inf,lstmn=inf;
    for(int v:e[u])if(!vis[v]){
        curmx=inf,curmn=inf;
        dfs4(v,u,max(a[u],a[v]),min(a[u],a[v]),1);
        ans=min(ans,min(lstmx+curmn+1,lstmn+curmx+1));
        lstmx=min(lstmx,curmx),lstmn=min(lstmn,curmn);
    }
	for(int v:e[u])if(!vis[v])
		rt=0,all=sz[v],dfs1(v,u),dfs2(rt);
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i],e[i].clear();
    for(int i=1;i<n;++i){
        cin>>x>>y;
        adde(x,y),adde(y,x);
    }
    ans=1e9;
    rt=0,all=n,mw[0]=n+1;
    memset(vis,0,sizeof(bool)*(n+1));
    dfs1(1,0),dfs2(rt);
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}