#include <bits/stdc++.h>
using namespace std;
#define maxn 100010

#define cn getchar
template<class TY>void read(TY &x){
	x=0;int f1=1;char ch=cn();
	while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
	if(x>9)write2(x/10);
	putchar(x%10+'0');
}
template<class TY>void write(TY x){
	if(x<0)putchar('-'),x=-x;
	write2(x);
}
int n;
int st[maxn][20],log_2[maxn];
vector<int> to[maxn],c[maxn];
int f[maxn][20],dep[maxn];
void dfs(int x,int deep){
	dep[x]=deep;
	c[deep].push_back(x);
	for(int y:to[x])if(y!=f[x][0]){
		f[y][0]=x;
		dfs(y,deep+1);
	}
}
int get_lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int j=17;j>=0;j--)
		if(dep[f[y][j]]>=dep[x])
			y=f[y][j];
	if(x==y)return x;
	for(int j=17;j>=0;j--)
		if(f[x][j]!=f[y][j])
			x=f[x][j],y=f[y][j];
	return f[x][0];
}
struct DSU{
	int fa[maxn];
	void init(const int N){
		for(int i=1;i<=N;i++)
			fa[i]=i;
	}
	int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
	void merge(int x,int y){
		x=findfa(x); y=findfa(y);
		if(x!=y)fa[x]=y;
	}
}ds;
pair<int,int> g[maxn];

int main()
{
	int Te;read(Te);while(Te--){
		read(n);
		for(int i=0;i<n;i++)
			read(st[i][0]);
		for(int i=1;i<=n;i++){
			to[i].clear();
			c[i].clear();
		}
		for(int i=1,x,y;i<n;i++){
			read(x);read(y);
			to[x].push_back(y);
			to[y].push_back(x);
		}
		dfs(1,1);
		for(int j=1;j<=17;j++)
			for(int i=0;i<n-(1<<j)+1;i++)
				st[i][j]=min(st[i][j-1], st[i+(1<<j-1)][j-1]);
		for(int i=2;i<=n;i++)
			log_2[i]=log_2[i>>1]+1;
		auto query=[&](int x,int y){
			if(x>y)return 1000000000;
			int lg=log_2[y-x+1];
			return min(st[x][lg], st[y-(1<<lg)+1][lg]);
		};
		for(int j=1;j<=17;j++)
			for(int i=1;i<=n;i++)
				f[i][j]=f[f[i][j-1]][j-1];
		ds.init(n);
		for(int i=1;i<=n;i++)g[i]=make_pair(i,st[0][0]);
		
		long long ans=0;
		for(int i=1;i<=n;i++)if(c[i].size()){
			vector<array<int,3>> d;
			for(int j=0;j<c[i].size()-1;j++){
				d.push_back({c[i][j], c[i][j+1], dep[get_lca(c[i][j],c[i][j+1])]});
			}
			sort(d.begin(),d.end(),[&](array<int,3> x,array<int,3> y){
				return x[2]<y[2];
			});
			for(auto j:d){
				int x=ds.findfa(j[0]), y=ds.findfa(j[1]);
				int lca = get_lca(g[x].first,g[y].first);
				// assert(dep[lca] == j[2]);
				g[x].second = min(g[x].second, query(i-dep[g[x].first], i-dep[lca]));
				g[y].second = min(g[y].second, query(i-dep[g[y].first], i-dep[lca]));
				int z=g[x].second + g[y].second;
				ds.fa[x]=y;
				g[y] = make_pair(lca,z);
			}
			int dg = ds.findfa(c[i][0]);
			g[dg].second = min(g[dg].second, query(i-dep[g[dg].first], i-dep[1]));
			ans += g[dg].second;
		}
		write(ans);puts("");
	}
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/