#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
	typedef long long ll;
	typedef pair<int,int> pii;
	template<typename T>
	il void read(T &x){
		int f=1;x=0;char c=gc();
		while(c<'0'||c>'9'){
			if(c=='-'){
				f=-1;
			}
			c=gc();
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-48,c=gc();
		}
		x*=f;
	}
	template<typename T,typename ...Args>
	void read(T &x,Args &...args){
		read(x),read(args...);
	}
	template<typename T>
	il void write(T x){
		char buf[43];int len=0;
		if(x<0){
			pc('-'),x=-x;
		}
		do{
			buf[++len]=x%10,x/=10;
		}while(x);
		while(len){
			pc(buf[len--]+'0');
		}
	}
}
using namespace my_std;
const int N=1e5+7,M=-1,inf=0x3f3f3f3f,mod=0;
int n,m,D,a[N],cur,dfn[N],dep[N],fa[N][17],dp[N];
vector<int> g[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
struct STable{
	int st[17][N];
	void init(){
		rep(i,1,n){
			st[0][i]=a[i];
		}
		rep(i,1,__lg(n)){
			rep(j,1,n-(1<<i)+1){
				st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
			}
		}
	}
	il int qry(int l,int r){
		int k=__lg(r-l+1);
		return min(st[k][l],st[k][r-(1<<k)+1]);
	}
}ST;
void dfs1(int u,int f){
	dfn[u]=++cur;
	g[dep[u]=dep[f]+1].eb(u);
	fa[u][0]=f;
	rep(i,1,16){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		dfs1(v,u);
	}
}
void dfs2(int u,int f){
	go(i,u){
		int v=e[i].to;
		dfs2(v,u);
		dp[u]+=dp[v];
	}
	if(!dp[u]){
		dp[u]=inf;
	}
	dp[u]=min(dp[u],ST.qry(D-dep[u]+1,D-dep[f]));
}
il int getLca(int u,int v){
	if(dep[u]<dep[v]){
		swap(u,v);
	}
	drep(i,16,0){
		if(dep[fa[u][i]]>=dep[v]){
			u=fa[u][i];
		}
	}
	if(u==v){
		return u;
	}
	drep(i,16,0){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i],v=fa[v][i];
		}
	}
	return fa[u][0];
}
il bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}
int solve(vector<int> f){
	sort(f.begin(),f.end(),cmp);
	int k=f.size()-1;
	rep(i,1,k){
		f.eb(getLca(f[i-1],f[i]));
	}
	sort(f.begin(),f.end(),cmp);
	f.erase(unique(f.begin(),f.end()),f.end());
	rep(i,1,(int)f.size()-1){
		add(getLca(f[i-1],f[i]),f[i]);
	}
	dfs2(1,0),tot=0;
	int ret=dp[1];
	for(int i:f){
		head[i]=dp[i]=0;
	}
	return ret;
}
void Yorushika(){
	read(n),tot=cur=0;
	rep(i,1,n){
		read(a[i]);
		head[i]=0,g[i].clear();
	}
	ST.init();
	rep(i,1,n-1){
		int u,v;read(u,v);
		add(u,v),add(v,u);
	}
	dfs1(1,0),tot=0;
	rep(i,1,n){
		head[i]=0;
	}
	ll ans=0;
	rep(i,1,n){
		if(!g[i].size()){
			break;
		}
		if(i>1){
			g[i].eb(1);
		}
		D=i,ans+=solve(g[i]);
	}
	printf("%lld\n",ans);
}
signed main(){
	int t=1;
	read(t);
	while(t--){
		Yorushika();
	}
}