#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
template<const int N,const int M>
struct graph
{
	int head[N+5];
	int ww[M+5];
	int t[M+5];
	int x[M+5];
	int cntm;
	graph(){ cntm=1;}
	inline void clear(int n=N)
	{
		cntm=1;
		for(int i=1;i<=n;i++) head[i]=0;
	}
	inline void ad(int u,int v,int w=0)
	{
		cntm++;
		t[cntm]=v;
		x[cntm]=head[u];
		ww[cntm]=w;
		head[u]=cntm;
	}
	inline void add(int u,int v,int w=0)
	{
		ad(u,v,w);
		ad(v,u,w);
	}
	inline int st(int num){ return head[num];}
	inline int to(int num){ return t[num];}
	inline int nx(int num){ return x[num];}
	inline int w(int num){ return ww[num];}
};
graph<100000,200000>g;
int st[21][100005];
int fa[21][100005];
vc<int>nod[100005];
int dep[100005];
int n;
inline void clear()
{
	g.clear(n);
	for(int i=1;i<=n;i++) nod[i].clear();
}
void dfs(int num)
{
	nod[dep[num]].push_back(num);
	for(int i=1;i<=16;i++) fa[i][num]=fa[i-1][fa[i-1][num]];
	for(int i=g.st(num);i;i=g.nx(i))
	{
		int p=g.to(i);
		if(p==fa[0][num]) continue;
		fa[0][p]=num,dep[p]=dep[num]+1,dfs(p);
	}
}
inline ll get(int l,int r)
{
	int num=31-__builtin_clz(r-l+1);
	// printf("get %d ~ %d : %d\n",l,r,min(st[num][l],st[num][r-(1<<num)+1]));
	return min(st[num][l],st[num][r-(1<<num)+1]);
}
inline int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=16;i>=0;i--) if(dep[u]-(1<<i)>=dep[v]) u=fa[i][u];
	if(u==v) return u;
	for(int i=16;i>=0;i--) if(fa[i][u]!=fa[i][v]) u=fa[i][u],v=fa[i][v];
	return fa[0][u];
}
ll dp[100001];
int sta[100001],top;
inline ll get(int D)
{
	int lst=0;dp[0]=0;assert(!top);
	for(int i:nod[D])
	{
		dp[i]=inf;
		if(!lst){ lst=sta[++top]=i;continue;}
		int p=lca(lst,i);lst=i;

		// printf("i=%d top=%d\n",i,sta[top]);
		while(top&&dep[sta[top]]>dep[p])
		{
			int t=sta[top--];
			int f=top?sta[top]:p;
			dp[t]=min(dp[t],get(D-dep[t],D-dep[f]-1));
			// printf("dp[%d]=%lld (f=%d)\n",t,dp[t],f);
			dp[f]+=dp[t];dp[t]=0;
		}
		if(sta[top]!=p) sta[++top]=p;
		sta[++top]=i;
	}
	while(top)
	{
		int t=sta[top--],f=sta[top];
		dp[t]=min(dp[t],get(D-dep[t],D-dep[f]-1));
		// printf("dp[%d]=%lld f=%d\n",t,dp[t],f);
		dp[f]+=dp[t];dp[t]=0;
	}
	// printf("D=%d : %lld\n",D,dp[0]);
	return dp[0];
}
inline void solve()
{
	clear();n=read();
	for(int i=0;i<n;i++) st[0][i]=read();
	for(int i=1;(1<<i)<=n;i++) for(int j=0;j+(1<<i)-1<n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	for(int i=1;i<n;i++) g.add(read(),read());
	dep[1]=1;dfs(1);ll ans=0;
	for(int i=1;nod[i].size();i++) ans+=get(i);
	printf("%lld\n",ans);
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/