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

#define ll long long

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
	while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
	return x * f;
}

#define pii pair<int, int>
#define mk make_pair
#define pb push_back

const int N = 1e5 + 10; const ll inf = 1e18;

int n, lg[N];

int st[18][N], w[N];

vector<int> e[N];

inline ll queryMin(int l, int r) {
	if (l > r) return inf;
	int d = lg[r-l+1];
	return min(st[d][l], st[d][r-(1<<d)+1]);
}

int fa[18][N], dep[N]; vector<int> vec[N];
inline void dfs(int u, int f, int d) {
	fa[u][0] = f; dep[u] = d;
	for (int i = 1; i < 18; ++ i) fa[u][i] = fa[fa[u][i-1]][i-1];
	vec[d].pb(u);
	for (auto v : e[u]) if (v ^ f) dfs(v, u, d+1);
}

inline int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v); 
	for (int i = 17; i >= 0; -- i) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i = 17; i >= 0; -- i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

vector<int> E[N];

int top, stc[N];

inline ll dp(int u, int fd, int d) {
	ll ret = 0;
	if (E[u].empty()) ret = inf;
	else {
		for (auto v : E[u])
			ret += dp(v, dep[u], d);
	} ret = min(ret, queryMin(d - dep[u], d - fd - 1));
	return ret;
}

inline ll calc(int d) {
	stc[top = 1] = 1; E[1].clear();
	for (auto u : vec[d]) {
		E[u].clear(); int c = lca(u, stc[top]);
		if (c == stc[top]) {
			stc[++ top] = u; 
		}  else {
			while (dep[stc[top-1]] > dep[c]) 
				E[stc[top-1]].pb(stc[top]), top --;
			if (c == stc[top-1]) {
				E[c].pb(stc[top]); top --;
			} else {
				E[c].clear(); E[c].pb(stc[top]); stc[top] = c;
			} stc[++ top] = u;
		}
	} while (top > 1) {
		E[stc[top-1]].pb(stc[top]); top --;
	} return dp(1, 0, d);
}

inline void solve() {
	n = read();
	for (int i = 0; i < n; ++ i) w[i] = read(), st[0][i] = w[i];
	for (int i = 1; i <= n; ++ i) e[i].clear();
	for (int i = 1; i <= 17; ++ i)
		for (int j = 0; j + (1 << i) - 1 < n; ++ j)
			st[i][j] = min(st[i-1][j], st[i-1][j+(1<<i-1)]);
	for (int i = 1, u, v; i < n; ++ i)
		u = read(), v = read(), e[u].pb(v), e[v].pb(u);
	for (int i = 1; i <= n; ++ i) vec[i].clear();
	dfs(1, 0, 1);
	ll ans = w[0];
	for (int i = 2; i <= n; ++ i) {
		if (vec[i].empty()) break;
		ans += calc(i);
	} printf("%lld\n", ans);
}

int main () {
	for (int i = 2; i < N; ++ i) lg[i] = lg[i >> 1] + 1;
	int T = read();
	while (T --) solve();
	return 0;
}
/*
3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4
*/