// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: E. Color the Tree
// Contest: Codeforces - The 2022 ICPC Asia Nanjing Regional Contest
// URL: https://codeforces.com/gym/104128/problem/E
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<int> G[N], D[N];
int f[N][M];
int dep[N];
long long a[N];
void dfs_dep(int u) {
	for (int i = 1; i < M; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	D[dep[u]].push_back(u);
	for (int v : G[u]) {
		if (v == f[u][0]) {
			continue;
		}
		f[v][0] = u, dep[v] = dep[u] + 1, dfs_dep(v);
	}
	return ;
}
int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int i = 0, dc = dep[u] - dep[v]; i < M; i++) {
		if ((dc >> i) & 1) {
			u = f[u][i];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = M - 1; ~ i; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i], v = f[v][i];
		}
	}
	return f[u][0];
}
vector<int> vG[N];
long long dfs_f(int u, int fa, int d) {
	long long res = LLONG_MAX;
	if (dep[u] == d);
	else {
		res = 0;
		for (int v : vG[u]) {
			res += dfs_f(v, u, d);
		}
	}
	long long mn = LLONG_MAX;
	for (int i = dep[fa] + 1; i <= dep[u]; i++) {
		mn = min(mn, a[d - i]);
	}
	return min(res, mn);
}
int stk[N], top;
long long calc(int d) {
	top = stk[1] = 1, vG[1].clear();
	for (int u : D[d]) {
		vG[u].clear();
		int l = LCA(u, stk[top]);
		if (l == stk[top]) {
			stk[++top] = u;
			continue;
		}
		for (; dep[l] < dep[stk[top - 1]]; top--) {
			vG[stk[top - 1]].push_back(stk[top]);
		}
		if (l == stk[top - 1]) {
			vG[l].push_back(stk[top]), top--;
		}
		else {
			vG[l].clear(), vG[l].push_back(stk[top]), stk[top] = l;
		}
		stk[++top] = u;
	}
	for (; top > 1; top--) {
		vG[stk[top - 1]].push_back(stk[top]);
	}
	return dfs_f(1, 0, d);
}
void solve() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);	
	}
	for (int i = 1; i <= n; i++) {
		G[i].clear();
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y), G[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		D[i].clear();	
	}
	dep[1] = 1;
	dfs_dep(1);
	long long ans = a[0];
	for (int i = 2; i <= n && ! D[i].empty(); i++) {
		ans += calc(i);
	}
	printf("%lld\n", ans);
	return ;
}
int main() {
	int _;
	scanf("%d", &_);
	for (; _; _--) {
		solve();
	}
	return 0;
}