#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=1e5+7,K=18;
ll n,a[N],dep[N],ans;
ll dfn[N],cnn,fa[N][K],dp[N];
ll m,b[N*2];
vector<ll> e[N],de[N],e1[N];
struct st {
	ll mn[K][N];
	void ini(ll n,ll *a) {
		for (ll i=1;i<=n;i++) mn[0][i]=a[i];
		for (ll i=1;i<K;i++) for (ll j=1;j+(1ll<<i)-1<=n;j++)
			mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1ll<<(i-1))]);
	}
	ll que(ll l,ll r) {
		return min(mn[__lg(r-l+1)][l],mn[__lg(r-l+1)][r-(1ll<<__lg(r-l+1))+1]);
	}
} T;
void dfs(ll p,ll f) {
	dfn[p]=++cnn,dep[p]=dep[f]+1,fa[p][0]=f;
	for (ll i=1;i<K;i++) fa[p][i]=fa[fa[p][i-1]][i-1];
	for (ll i:e[p]) if (i!=f) dfs(i,p);
}
ll lca(ll x,ll y) {
	if (dep[x]<dep[y]) swap(x,y);
	for (ll i=K-1;~i;i--) if (dep[x]-dep[y]>=1ll<<i) x=fa[x][i];
	if (x==y) return x;
	for (ll i=K-1;~i;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void dfs1(ll p,ll f,ll d) {
	dp[p]=0;
	for (ll i:e1[p]) if (i!=f) dfs1(i,p,d),dp[p]+=dp[i];
	ll w=T.que(d-dep[p]+1,d-dep[f]);
	if (!dp[p]) dp[p]=w;
	else dp[p]=min(dp[p],w);
}
void solve(ll d) {
	b[m=1]=1; for (ll i:de[d]) b[++m]=i;
	for (ll i=1;i<=m;i++) b[m+i]=lca(b[i],b[i+1]);
	m=m*2-1,sort(b+1,b+m+1,[](ll x,ll y){return dfn[x]<dfn[y];});
	m=unique(b+1,b+m+1)-1-b;
	for (ll i=2;i<=m;i++) {
		ll x=lca(b[i-1],b[i]);
		e1[x].pb(b[i]),e1[b[i]].pb(x);
	}
	dfs1(1,0,d);
	ans+=dp[1];
	for (ll i=1;i<=m;i++) e1[b[i]].clear();
}
void mian() {
	scanf("%lld",&n),ans=cnn=0;
	for (ll i=1;i<=n;i++) scanf("%lld",&a[i]),e[i].clear(),de[i].clear();
	T.ini(n,a);
	for (ll i=1,x,y;i<n;i++) scanf("%lld%lld",&x,&y),e[x].pb(y),e[y].pb(x);
	dfs(1,0);
	for (ll i=1;i<=n;i++) de[dep[i]].pb(i);
	for (ll i=1;i<=n;i++) if (de[i].size()) solve(i);
	cout<<ans<<"\n";
}
bool ORY; int main() {
	// while (1)
	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB\n";
	return 0;
}