#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mk make_pair
#define fi first
#define se second

inline int read(){
	int t = 0,f = 1;
	register char c = getchar();
	while (c < 48 || c > 57) f = (c == '-') ? (-1) : (f),c = getchar();
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
	return f * t;
}

const int N = 1e5 + 10,LOGN = 17 + 1;
int T,n,idcnt,a[N],id[N],dep[N],mxdep[N],son[N],top[N],fa[N],dwn[N],lst[N];
int mlg[1 << LOGN],mn[LOGN][N];
ll dp[N];

vector <int> G[N];

void init(){
	mlg[0] = -1;
	for (int i = 1;i <= n;i++) mlg[i] = mlg[i >> 1] + 1;
	for (int i = 0;i < n;i++) mn[0][i] = a[i];
	for (int i = 1;i < LOGN;i++){
		for (int j = 0;j < n;j++){
			mn[i][j] = mn[i - 1][j];
			if (j + (1 << (i - 1)) < n) mn[i][j] = min(mn[i][j],mn[i - 1][j + (1 << (i - 1))]);
		}
	}
}

inline int getmn(int l,int r){
	int t = mlg[r - l + 1];
	return min(mn[t][l],mn[t][r - (1 << t) + 1]);
}

void dfs0(int u,int f){
	mxdep[u] = dep[u] = dep[f] + 1,fa[u] = f;
	son[u] = 0;
	for (int v : G[u]){
		if (v == f) continue;
		dfs0(v,u),mxdep[u] = max(mxdep[u],mxdep[v]);
		if (mxdep[v] > mxdep[son[u]]) son[u] = v;
	}
}

void dfs1(int u,int t){
	id[u] = ++idcnt,top[u] = t,dwn[t] = max(dwn[t],id[u]);
	if (son[u]) dfs1(son[u],t);
	for (int v : G[u]){
		if (v == fa[u] || v == son[u]) continue;
		dfs1(v,v);
	}
}

void upd(int u,int d){
	if (lst[u] >= d) return ;
	ll v = getmn(lst[u] + 1,d);
	dp[u] = min(dp[u],v);
	lst[u] = d;
}

void DP(int u){
	for (int v : G[u]){
		if (v == fa[u]) continue;
		DP(v);
	}
	dp[id[u]] = a[0],lst[id[u]] = 0;
	int mxd = 0;
	for (int v : G[u]){
		if (v == fa[u] || v == son[u]) continue;
		mxd = max(mxd,mxdep[v]);
	}
	for (int v : G[u]){
		if (v == fa[u] || v == son[u]) continue;
		for (int i = id[v];i <= dwn[v];i++){
			dp[id[u] + i - id[v] + 1] += dp[i];
		}
	}
	for (int i = id[u];i <= id[u] + mxd - dep[u];i++){
		upd(i,i - id[u]);
	}
}

void solve(){
	n = read();
	for (int i = 0;i < n;i++) a[i] = read();
	init();
	for (int i = 1;i <= n;i++) G[i].clear(),dwn[i] = 0;
	for (int i = 1;i < n;i++){
		int u = read(),v = read();
		G[u].emplace_back(v),G[v].emplace_back(u);
	}
	idcnt = 0;
	dfs0(1,0);
	dfs1(1,1);
	DP(1);
	ll ans = 0;
	for (int i = id[1];i <= dwn[1];i++){
		upd(i,i - id[1]);
		ans += dp[i];
	}
	printf("%lld\n",ans);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	T = read();
	while (T--) solve();
	return 0;
}