#include <bits/stdc++.h>
using i64 = long long;

template<typename T>
inline void chkmin(T &a, const T &b) {if (a > b) a = b;}
constexpr int N = 1e5 + 10;
constexpr i64 inf = 1e18;

int n;
std::basic_string<int> G[N];
i64 f[N][3];
int a[N];

inline void add(int u, int v) {
	G[u].push_back(v);
}
inline void clear() {
	for (int i = 1; i <= n; i++) {
		G[i].clear();
		f[i][0] = f[i][1] = f[i][2] = 0;
	}
}
void dfs(int u, int fa) {
	i64 sum = 0;
	for (const int &v : G[u]) {
		if (v == fa)
			continue;
		dfs(v, u);
		f[u][1] += std::min({f[v][0], f[v][1], f[v][2]});
		f[u][2] += std::min({f[v][0], f[v][1]});
		sum += std::min(f[v][0], f[v][1]);
	}

	f[u][0] = inf;
	for (const int &v : G[u]) {
		if (v == fa)
			continue;
		chkmin(f[u][0], sum - std::min(f[v][0], f[v][1]) + f[v][1]);
	}
}

void solve() {
	std::cin >> n;
	clear();
	for (int i = 1; i <= n; i++)
		std::cin >> f[i][1];
	if (n == 1) {
		std::cout << f[1][1] << '\n';
		return ;
	}
	for (int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1, 0);
	std::cout << std::min(f[1][0], f[1][1]) << '\n';
}

int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int T;
	std::cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}