#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define drp(i,j,k) for(int i=j;i>=(k);--i)
#define MAXN 1000005
typedef long long ll;
inline int read(){
	int x=0;
	bool sgn=true;
	char ch=getchar();
	while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return sgn?x:-x;
}
inline void chkmin(int &x,int y){x=std::min(x,y);}
int n,ans,a[MAXN],dep[MAXN],val[MAXN];
std::vector<int> edge[MAXN];
inline void init(){
	ans=1e9;
	rep(i,1,n) a[i]=dep[i]=val[i]=0;
	rep(i,1,n) std::vector<int>().swap(edge[i]);
}
inline void dfs1(int u,int fa){
	dep[u]=dep[fa]+1,val[u]=dep[u]-a[u];
	for(auto v:edge[u]){
		if(v==fa) continue;
		dfs1(v,u),chkmin(val[u],val[v]);
	}
}
inline void dfs2(int u,int fa,int ret){
	chkmin(ret,1-a[u]);
	chkmin(ans,a[u]+ret);
	chkmin(ans,a[u]+val[u]-dep[u]+1);
	std::set<std::pair<int,int>> set;
	set.insert(std::make_pair((int)1e9,0));
	for(auto v:edge[u]) if(v!=fa) set.insert(std::make_pair(val[v],v));
	for(auto v:edge[u]){
		if(v==fa) continue;
		auto it=set.begin();
		if(it->second==v) ++it;
		dfs2(v,u,std::min(ret,it->first)+1);
	}
}
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0),std::cout.tie(0);
	drp(task,read(),1){
		n=read(),init();
		rep(i,1,n) a[i]=read();
		rep(i,1,n-1){
			int u=read(),v=read();
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		dfs1(1,0),dfs2(1,0,(int)1e9);
		printf("%d\n",ans);
	}
}