#include<bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define int long long
using namespace std;

inline int rd(){
	int s=0, f=1; char c=getchar();
	while(!isdigit(c)) f^=(c=='-'), c=getchar();
	while(isdigit(c)) s=s*10+c-'0', c=getchar();
	return f? s:-s;
}

void wt(int x, char c=0){
	if(x<0) return putchar('-'), wt(-x, c);
	if(x>9) wt(x/10); putchar(x%10+'0');
	if(c) putchar(c);
}

const int N=1e5+5;

int n, a[N], mxd, anc[N][22], dep[N]={-1}, mx[N];
vector<int> e[N];

int get_lca(int u, int v){
	if(dep[v]<dep[u]) swap(u, v);
	int dif=dep[v]-dep[u];
	for(int i=20; ~i; i--) if(dif>>i&1) u=anc[u][i];
	if(u==v) return u;
	for(int i=20; ~i; i--) if(anc[u][i]!=anc[v][i]) u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}

vector<int> vec[N];
int nxt[N];

namespace ST{

int st[N][22];

void init(){
	for(int i=0; i<n; i++) st[i][0]=a[i];
	for(int j=1; (1<<j)<=n; j++)
		for(int i=0; i+(1<<j)-1<n; i++) st[i][j]=min(st[i][j-1], st[i+(1<<j-1)][j-1]);
}

int que(int l, int r){
	int k=__lg(r-l+1);
	return min(st[l][k], st[r-(1<<k)+1][k]);
}

}

void solve(){
	n=rd();
	for(int i=0; i<n; i++) a[i]=rd();
	for(int i=1, u, v; i<n; i++){
		u=rd(), v=rd();
		e[u].push_back(v);
		e[v].push_back(u);
	}
	//init
	function<void(int, int)> dfs=[&](int u, int fa){
		mx[u]=dep[u]=dep[fa]+1;
		mxd=max(mxd, dep[u]);
		anc[u][0]=fa;
		for(int i=1; (1<<i)<=20; i++) anc[u][i]=anc[anc[u][i-1]][i-1];
		for(int v:e[u]) if(v!=fa) dfs(v, u), mx[u]=max(mx[u], mx[v]);
	};
	dfs(1, 0);
	for(int i=1; i<=n; i++) vec[dep[i]].push_back(i);
	nxt[0]=-1;
	for(int i=1; i<=mxd; i++){
		nxt[i]=0;
		for(int j=0; j+1<vec[i].size(); j++){
			nxt[i]=max(nxt[i], dep[get_lca(vec[i][j], vec[i][j+1])]);
		}
		sort(vec[i].begin(), vec[i].end(), [](int u, int v){
			return mx[u]>mx[v];
		});
	}
	ST::init();
	//

	//calc ans
	int ans=0;
	for(int i=0; i<=mxd; i++){
		int cur=1e18;
		for(int j=i; ~j; j=nxt[j]){
			int l=i-j, r=i-nxt[j]-1;
			int L=0, R=vec[j].size();
			while(R-L>1){
				int mid=(L+R)/2;
				if(mx[vec[j][mid]]>=i) L=mid;
				else R=mid;
			}
			cur=min(cur, ST::que(l, r)*(L+1));
		}
		ans+=cur;
	}
	//

	wt(ans, '\n');

	for(int i=0; i<=n; i++){
		e[i].clear();
		vec[i].clear();
		memset(anc[i], 0, sizeof(anc[i]));
	}
	mxd=0;
}

signed main(){
	int T=rd();
	while(T--){
		solve();
	}
	return 0;
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/