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

const int N = 1e5 + 10;
int n, dfncnt, rt;
int a[N], dfn[N], dep[N], lg2[N], fa[N][18];
long long dp[N], stc[N][18];
vector<int> g[N], h[N], vtp, vt[N], imp;

void init(){
	dfncnt = 0;
	vtp.clear();
	for(int i = 0; i <= n; i++){
		g[i].clear(), h[i].clear(), vt[i].clear();
		dep[i] = dfn[i] = dp[i] = a[i] = 0;
		for(int j = 0; j < 18; j++) {
			stc[i][j] = 1e18;
			fa[i][j] = 0;
		}
	}
	n = rt = 0;
	return ;
}

inline long long query_min(int l, int r){
	l++, r++;
	int T = lg2[r - l + 1];
	return min(stc[l][T], stc[r - (1 << T) + 1][T]);
}

void dfs(int u, int pre){
	dfn[u] = ++dfncnt;
	dep[u] = dep[pre] + 1; h[dep[u]].push_back(u);
	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)
		dfs(v, u);
	return ;
}
inline int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 17; i >= 0; i--)
		if(dep[fa[x][i]] >= dep[y])
			x = fa[x][i];
	if(x == y) return x;
	for(int i = 17; i >= 0; i--)
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline void build_virtual_tree(){
	sort(imp.begin(), imp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
	vtp.clear();
	for(int i = 0; i < imp.size() - 1; i++)
		vtp.push_back(imp[i]), vtp.push_back(lca(imp[i], imp[i + 1]));
	vtp.push_back(imp.back());
	sort(vtp.begin(), vtp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
	int len = unique(vtp.begin(), vtp.end()) - vtp.begin();
	for(int i : vtp) vt[i].clear();
	for(int i = 0, lc; i < len - 1; i++){
		lc = lca(vtp[i], vtp[i + 1]);
		vt[lc].push_back(vtp[i + 1]);
	}
	rt = vtp[0];
	return ;
}

void dfs_on_vt(int u, int pre, int D){
	dp[u] = (!vt[u].size()) * 1e18;
	for(int v : vt[u]){
		dfs_on_vt(v, u, D);
		dp[u] += dp[v];
	}
	dp[u] = min(dp[u], query_min(D - dep[u], D - dep[pre] - 1));
	return ;
}

void work(){
	init();

	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], stc[i][0] = a[i];
	for(int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
	for(int i = 1; i <= 17; i++)
		for(int j = 1; j + (1 << i) - 1 <= n; j++)
			stc[j][i] = min(stc[j][i - 1], stc[j + (1 << (i - 1))][i - 1]);

	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);

	long long ans = 0;
	for(int i = 1; i <= n; i++) if(h[i].size()){
		imp = h[i];
		build_virtual_tree();
		dfs_on_vt(rt, 0, i);
		ans += dp[rt];
	}
	cout << ans << "\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T--) work();
	return 0;
}