#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+10;
const int N=1e5;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n;
long long ans=0;
int a[MAXN],Log[MAXN];
namespace ST{
	int st[18][MAXN];
	inline void build(){
		for(int i=1;i<=n;i++)
		{
			st[0][i]=a[i];
		}
		for(int i=1;i<=Log[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))]);
			}
		}
	}
	inline int query(int l,int r){
		int g=Log[r-l+1];
		return min(st[g][l],st[g][r-(1<<g)+1]);
	}
}
basic_string <int> tr[MAXN];
inline void add_edge(int x,int y){
	tr[x].push_back(y);
}
int dfc=0;
int dad[MAXN],dfn[MAXN],dep[MAXN];
basic_string <int> s[MAXN];
void dfs(int x){
	dep[x]=dep[dad[x]]+1;
	s[dep[x]].push_back(x);
	dfc++;
	dfn[x]=dfc;
	for(int to:tr[x])
	{
		if(to^dad[x]){
			dad[to]=x;
			dfs(to);
		}
	}
}
namespace ST_LCA{
	int st[18][MAXN];
	#define calc(x,y) dfn[x]<dfn[y]?x:y
	inline void build(){
		for(int i=1;i<=n;i++)
		{
			st[0][dfn[i]]=dad[i];
		}
		for(int i=1;i<=Log[n];i++)
		{
			for(int j=1;j+(1<<i)-1<=n;j++)
			{
				st[i][j]=calc(st[i-1][j],st[i-1][j+(1<<(i-1))]);
			}
		}
	}
	inline int lca(int x,int y){
		if(x==y){
			return x;
		}
		x=dfn[x];
		y=dfn[y];
		if(x>y){
			swap(x,y);
		}
		x++;
		int g=Log[y-x+1];
		return calc(st[g][x],st[g][y-(1<<g)+1]);
	}
}
using ST_LCA::lca;
basic_string <int> vtr[MAXN];
inline void add_vtr(int x,int y){
	vtr[x].push_back(y);
}
int cur;
int dp[MAXN];
void Dfs(int x,int f){
	int res=ST::query(cur-dep[x]+1,cur-dep[f]+1);
	if(dep[x]==cur){
		dp[x]=res;
		return ;
	}
	dp[x]=0;
	for(int to:vtr[x])
	{
		Dfs(to,x);
		dp[x]+=dp[to];
		dp[x]=min(dp[x],res);
	}
}
inline void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		s[i].clear();
		tr[i].clear();
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dfc=0;
	dfs(1);
	for(int i=2;i<=n;i++)
	{
		Log[i]=Log[i>>1]+1;
	}
	ST::build();
	ST_LCA::build();
	ans=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i].empty()){
			break;
		}
		int siz=s[i].size();
		for(int j=0;j<siz-1;j++)
		{
			s[i].push_back(lca(s[i][j],s[i][j+1]));
		}
		s[i].push_back(1);
		sort(s[i].begin(),s[i].end());
		s[i].erase(unique(s[i].begin(),s[i].end()),s[i].end());
		siz=s[i].size();
		for(int x:s[i])
		{
			vtr[x].clear();
		}
		for(int j=1;j<siz;j++)
		{
			add_vtr(lca(s[i][j-1],s[i][j]),s[i][j]);
		}
		cur=i;
		Dfs(1,1);
		ans+=dp[1];
	}
	printf("%lld\n",ans);
}
signed main(){
	#ifdef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
	#endif
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}