#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
using namespace std;
constexpr int N=1e5+5;
int n,tim,cost[N],dfn[N],out[N],dep[N],mn[N][17],st[N+N][18];
vector<int>G[N],E[N],ele[N];
inline int getmn(int l,int r)
{
	int k=log2(r-l+1);
	return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline int dcmp(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline int lca(int x,int y)
{
//	printf("[x y dfnx dfny] %d %d %d %d\n",x,y,dfn[x],dfn[y]);
	x=dfn[x],y=dfn[y];
	if(x>y)swap(x,y);
	int k=log2(y-x+1);
	return dcmp(st[x][k],st[y-(1<<k)+1][k]);
}
inline ll sol(int x,int fa,const int D)
{
	if(E[x].empty())return getmn(D-dep[x],D-dep[fa]-1);
	ll sum=0;
	for(auto y:E[x])sum+=sol(y,x,D);
	return min(sum,(ll)getmn(D-dep[x],D-dep[fa]-1));
}
inline ll solve(vector<int>s,int d)
{
//	printf("d=%d\n", d);
//	for(auto x:s) printf("%d ",x); puts("");
	sort(s.begin(),s.end(),[&](int x,int y){return dfn[x]<dfn[y];});
	vector<int>cur=s;int lst=0;
	for(auto x:cur)
	{
		if(lst)cur.emplace_back(lca(x,lst));
		lst=x;
	}
	cur.emplace_back(1);
	sort(cur.begin(),cur.end(),[&](int x,int y){return dfn[x]<dfn[y];});
	cur.resize(unique(cur.begin(),cur.end())-cur.begin()),lst=0;
	vector<int>redo;
	for(auto x:cur)
	{
		if(lst)
		{
			int p=lca(x,lst);
			E[p].emplace_back(x);
			redo.emplace_back(p);
		}
		lst=x;
	}
	ll ans=sol(1,0,d);
	for(auto x:redo)E[x].clear();
	return ans;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n,tim=0;
		rep(i,0,n-1)cin>>cost[i],mn[i][0]=cost[i];
		rep(j,1,16)rep(i,0,n-(1<<j))mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
		rep(i,1,n)dfn[i]=out[i]=dep[i]=0,ele[i].clear(),G[i].clear();
		rep(i,2,n)
		{
			int u,v;cin>>u>>v;
			G[u].emplace_back(v),G[v].emplace_back(u);
		}
		auto dfs=[&](int x,int fa,auto dfs)->void
		{
			st[dfn[x]=++tim][0]=x;
			ele[dep[x]=dep[fa]+1].emplace_back(x);
			for(auto y:G[x])
			{
				if(y==fa)continue;
				dfs(y,x,dfs),st[++tim][0]=x;
			}
			out[x]=tim;
		};
		dfs(1,0,dfs);
		rep(j,1,17)rep(i,1,tim-(1<<j)+1)st[i][j]=dcmp(st[i][j-1],st[i+(1<<j-1)][j-1]);
//		rep(i,1,n)rep(j,1,n)printf("lca(%d %d)=%d\n",i,j,lca(i,j));
		ll ans=0;
		rep(i,1,n)if(!ele[i].empty())ans+=solve(ele[i],i);
		cout<<ans<<'\n';
	}
	return 0;
}
/*
 3
 4
 10 15 40 1
 1 2
 2 3
 2 4
 5
 10 5 1 100 1000
 1 2
 2 3
 2 4
 4 5
 4
 1000 200 10 8
 1 2
 2 3
 3 4
*/