#include <iostream>
#include <cassert>
#include <vector>
typedef long long LL;
template <class T> using Arr = std::vector<T>;
template <class T> struct Wnd : Arr<T> {
	Arr<int> history;
	inline T &operator[](size_t x) { return Arr<T>::operator[]((x + this->size()) % this->size()); }
	void push_back(const T &x) { history.push_back(x); Arr<T>::push_back(x); }
};

const int MAXN = 100002;
int n, a[MAXN], dep[MAXN], dfn[MAXN], fa[20][MAXN];
Arr<int> e[MAXN], dbuk[MAXN], g[MAXN];
int st[20][MAXN];
LL f[MAXN];

void add_dir(int u, int v, Arr<int> e[]) {
	// printf("add %d %d\n", u, v);
	e[u].push_back(v);
}

void add(int u, int v) {
	e[u].push_back(v);
	e[v].push_back(u);
}

void dfs(int p) {
	for (int i = 1; i < 20; ++i)
		fa[i][p] = fa[i - 1][fa[i - 1][p]];
	dfn[p] = ++dfn[0];
	dbuk[dep[p]].push_back(p);
	for (auto to : e[p])
		if (to != fa[0][p]) {
			dep[to] = dep[p] + 1;
			fa[0][to] = p;
			dfs(to);
		}
}

int ask_min(int l, int r) {
	int len = r - l;
	int p = 0;
	while ((1 << (p + 1)) <= len)
		++p;
	// printf("askmin %d %d\n", l, r);
	// printf("askmin (%d %d) = %d\n", l, r, std::min(st[p][l], st[p][r - (1 << p)]));
	return std::min(st[p][l], st[p][r - (1 << p)]);
}

int LCA(int u, int v) {
	if (dep[u] < dep[v])
		std::swap(u, v);
	for (int i = 20 - 1; i >= 0; --i)
		if (dep[u] - (1 << i) >= dep[v])
			u = fa[i][u];
	if (u == v)
		return u;
	for (int i = 20 - 1; i >= 0; --i)
		if (fa[i][u] != fa[i][v])
			u = fa[i][u], v = fa[i][v];
	return fa[0][u];
}

void dfs1(int p, const int &D) {
	// printf("dfs1 %d %d\n", p, D);
	if (dep[p] == D)
		f[p] = a[0];
	else {
		f[p] = 0;
		for (auto to : g[p]) {
			dfs1(to, D);
			f[p] += f[to];
		}
		f[p] = std::min(f[p], (LL)ask_min(1, D - dep[p] + 1));
	}
}

LL work(int depth) {
	Wnd<int> sta;
	Arr<int> &now = dbuk[depth];
	sta.push_back(1);
	for (int i = 0; i < (int)now.size(); ++i) {
		int d = LCA(sta[-1], now[i]);
		while (dfn[sta[-1]] > dfn[d]) {
			if (dfn[sta[-2]] > dfn[d])
				add_dir(sta[-2], sta[-1], g);
			else
				add_dir(d, sta[-1], g);
			sta.pop_back();
		}
		if (sta[-1] != d)
			sta.push_back(d);
		if (sta[-1] != now[i])
			sta.push_back(now[i]);
	}
	while (sta.size() >= 2)
		add_dir(sta[-2], sta[-1], g), sta.pop_back();

	// printf("# ");
	// for (auto x : sta.history)
	// 	printf("%d ", x);
	// puts("");

	assert(sta.size() == 1);
	dfs1(sta[0], depth);

	for (auto x : sta.history)
		g[x].clear();

	return f[sta[0]];
}

void Solve() {
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		std::cin >> a[i];
		st[0][i] = a[i];
	}
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i + (1 << j) <= n; ++i)
			st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
	for (int i = 1; i < n; ++i) {
		int u, v;
		std::cin >> u >> v;
		add(u, v);
	}
	dfn[0] = 0;
	dfs(1);
	LL ans = 0;
	for (int i = 0; i < n; ++i)
		if (dbuk[i].size())
			ans += work(i);
	printf("%lld\n", ans);

	dfn[0] = 0;
	for (int i = 0; i < n; ++i)
		dbuk[i].clear();
	for (int i = 1; i <= n; ++i)
		e[i].clear();
}

int main() {
	std::ios::sync_with_stdio(false);
	int T;
	std::cin >> T;
	while (T--)
		Solve();
	return 0;
}