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

inline ll rd() {
	ll x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int maxn=1e6+10;

int n,C,ans,a[maxn];
int ma[maxn],siz[maxn],vis[maxn],ansma[maxn],ansmi[maxn];
vector<int>G[maxn];

void get_cen(int u,int fa,int Siz)
{
	siz[u]=1;
	ma[u]=-1;
	for(auto v:G[u])
	{
		if(v==fa||vis[v]) continue;
		get_cen(v,u,Siz);
		siz[u]+=siz[v];
		ma[u]=max(ma[u],siz[v]);
	}
	ma[u]=max(ma[u],Siz-siz[u]);
	if(C==-1||ma[C]>ma[u]) C=u;
}

void update(int u,int fa,int d)
{
	ansma[u]=d-a[u];
	ansmi[u]=d+a[u];
	siz[u]=1;
	for(auto v:G[u])
	{
		if(v==fa||vis[v]) continue;
		update(v,u,d+1);
		ansma[u]=min(ansma[u],ansma[v]);
		ansmi[u]=min(ansmi[u],ansmi[v]);
		siz[u]+=siz[v];
	}
}

void divide(int u,int Siz)
{
	C=-1;
	get_cen(u,0,Siz);
	vis[C]=1;
	update(C,0,0);
	ans=min(ans,ansma[C]+ansmi[C]+1);
	int nw=C;
	for(auto v:G[nw])
	{
		if(vis[v]) continue;
		divide(v,siz[v]);
	}
}

int main() {
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			G[i].clear();
			vis[i]=0;
		}
		for(int i=1,u,v;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		ans=0x3f3f3f3f;
		divide(1,n);
		printf("%d\n",ans);
	}
	return 0;
}