#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
vector<int> G[N],g[N],D[N];
int T,n,st[25][N],dfn[N],cnt=0,d[N],fa[N][25],x[N],dp[N];
void dfs1(int u,int pre,int dep) {
	D[dep].push_back(u);
	dfn[u]=++cnt,d[u]=dep,fa[u][0]=pre;
	for(int i=1; i<=20; i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int v:G[u]) {
		if(v==pre) continue;
		dfs1(v,u,dep+1);
	}
}
int lca(int u,int v) {
	if(d[u]<d[v]) swap(u,v);
	for(int i=20; i>=0; i--) if(d[fa[u][i]]>=d[v]) u=fa[u][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int calc(int l,int r) {
	int tmp=__lg(r-l+1);
	return min(st[tmp][l],st[tmp][r-(1<<tmp)+1]);
}
bool cmp(int a,int b) {return dfn[a]<dfn[b];}
void dfs2(int u,int pre,int dep) {
	if(g[u].empty()) {
		dp[u]=calc(dep-d[u]+1,dep-d[pre]);
		return;
	}
	dp[u]=0;
	for(int v:g[u]) {
		if(v==pre) continue;
		dfs2(v,u,dep);
		dp[u]+=dp[v];
	}
	dp[u]=min(dp[u],calc(dep-d[u]+1,dep-d[pre]));
}
void work() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>st[0][i];
	for(int i=1; (1<<i)<=n; i++) for(int j=1; 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++) {
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	cnt=0;
	dfs1(1,0,1);
	int ans=0;
	for(int i=1; i<=n; i++) {
		if(D[i].empty()) break;
		int tot=0;
		for(int j:D[i]) x[++tot]=j;
		x[++tot]=1;
		sort(x+1,x+tot+1,cmp);
		int tmp=tot;
		for(int i=1; i<tmp; i++) x[++tot]=lca(x[i],x[i+1]);
		sort(x+1,x+tot+1);
		int len=unique(x+1,x+tot+1)-x-1;
		for(int i=1; i<len; i++) g[lca(x[i],x[i+1])].push_back(x[i+1]);
		dfs2(1,0,i);
		ans+=dp[1];
		for(int i=1; i<len; i++) g[lca(x[i],x[i+1])].clear();
	}
	cout<<ans<<"\n";
	for(int i=1; i<=n; i++) G[i].clear(),D[i].clear();
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>T;
	while(T--) work();
	return 0;
}