#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define pb push_back
#define lowbit(x) (x)&-(x)
using namespace std;
const int N=1e5+10;
ll f[N],ans;
vi G[N],pos[N],tr[N];
int n,m,T,a[N],dfn[N],tot,anc[N][20],mn[N][20],dep[N];
inline int read(){
	int s=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return f?-s:s;
}
inline int cmin(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	pos[dep[x]].pb(x);
	dfn[x]=++tot;anc[tot][0]=fa;
	for(int to:G[x]) if(to!=fa) dfs(to,x);
}
inline int lca(int x,int y){
	if(x==y) return x;
	if((x=dfn[x])>(y=dfn[y])) swap(x,y);
	int k=__lg(y-x++);
	return cmin(anc[x][k],anc[y-(1<<k)+1][k]);
}
inline int query(int l,int r){
	int k=__lg(r-l+1);
	return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
inline void dfs(int x,int fa,int d){
	f[x]=0;
	for(int to:tr[x]) dfs(to,x,d),f[x]+=f[to];
	ll val=query(d-dep[x]+1,d-dep[fa]);
	if(tr[x].empty()) f[x]=val;
	else f[x]=min(f[x],val);
}
int main(){
	T=read();
	while(T--){
		n=read();
		for(register int i=1;i<=n;++i) a[i]=read(),G[i].clear(),pos[i].clear();
		for(register int i=1;i<n;++i){
			int u=read(),v=read();
			G[u].pb(v),G[v].pb(u);
		}
		dfs(1,0);
		for(register int i=1;i<=n;++i) mn[i][0]=a[i];
		for(register int i=1;i<=19;++i){
			for(register int j=1;j+(1<<i)-1<=n;++j){
				mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]);
				anc[j][i]=cmin(anc[j][i-1],anc[j+(1<<(i-1))][i-1]);
			}
		}
		ans=0;
		for(register int i=1;i<=n;++i){
			if(pos[i].empty()) continue;
			vi tmp;
			for(int x:pos[i]) tmp.pb(x);
			for(register int j=0;j+1<(int)pos[i].size();++j) tmp.pb(lca(pos[i][j],pos[i][j+1]));
			sort(tmp.begin(),tmp.end(),[](int x,int y){return dfn[x]<dfn[y];});
			tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
			for(int x:tmp) tr[x].clear();
			for(register int j=1;j<(int)tmp.size();++j) tr[lca(tmp[j],tmp[j-1])].pb(tmp[j]);
			dfs(tmp[0],0,i);
			ans+=f[tmp[0]];
			//~ cout<<ans<<"\n";
		}
		cout<<ans<<'\n';
	}
}