#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod 998244353
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l , r)(rng);}
template<typename T> inline void read (T &t) {
	t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
	while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
	while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
	if (ch == '.') {
		ch = getchar();
		while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
	}
	t = (f ? -t : t);
}
template <typename T, typename... Args>
	inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
	if (x >= 10) write(x / 10);
	cout << (ll) (x % 10);
}
const int N = 2e5 + 2, INF = 1e18 + 2;
int n, a[N], head[N], pos;
int ans;
struct Seg_tree {
	int tree[N << 2];
	inline void pushup (int rt) {
		tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]); }
	inline void build (int rt, int l, int r) {
		if (l == r) {
			tree[rt] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	inline int query (int rt, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tree[rt];
		int mid = (l + r) >> 1, ret = INF;
		if (L <= mid) ret = min(ret, query(rt << 1, l, mid, L, R));
		if (R > mid) ret = min(ret, query(rt << 1 | 1, mid + 1, r, L, R));
		return ret;
	}
}seg_tree;
struct Edge { int to, next; }edge[N << 1];
inline void add_edge (int u, int v) {
	edge[++pos] = (Edge) {v, head[u]}, head[u] = pos; }
int dfn[N], dfc, dep[N], son[N], mxdep[N], fath[N], top[N];
vector<pii > f[N];
inline void merge (int u, int v) {
	int size1 = (int)f[u].size(), size2 = (int)f[v].size();
	rep (i, 0, size2 - 1) {
		int d = size2 - i + dep[v] - 1, p = size1 + dep[u] - d - 1;
		f[u][p].fir = min(f[u][p].fir, seg_tree.query(1, 0, n - 1, d - f[u][p].sec, d - dep[u])) + min(f[v][p].fir, seg_tree.query(1, 0, n - 1, d - f[v][p].sec, d - dep[v]));
		f[u][p].sec = dep[u];
	}
}
inline void dfs1 (int u, int fa) {
	dep[u] = dep[fa] + 1, fath[u] = fa;
	go (i, u) {
		int v = edge[i].to;
		if (v == fa) continue;
		dfs1(v, u);
		if (dep[v] > mxdep[u]) son[u] = v, mxdep[u] = dep[v];
	}
}
inline void dfs2 (int u, int Top) {
	dfn[u] = ++dfc, top[u] = Top;
	go (i, u) {
		int v = edge[i].to;
		if (v == fath[u]) continue;
		if (son[u] == v) dfs2(v, Top);
		else dfs2(v, v);
	}
	if (!son[u]) f[u].emplace_back(MP(a[0], dep[u]));
	else {
		swap(f[u], f[son[u]]), f[son[u]].clear();
		f[u].emplace_back(MP(a[0], dep[u]));
		go (i, u) {
			int v = edge[i].to;
			if (v == fath[u] || v == son[u]) continue;
			merge(u, v), f[v].clear();
		}
	}
}
int T;
signed main() {
	read(T);
	while (T--) {
		memset(head, 0, sizeof head), memset(mxdep, 0, sizeof mxdep), memset(son, 0, sizeof son);
		ans = pos = dfc = 0;
		read(n);
		rep (i, 0, n - 1) read(a[i]);
		seg_tree.build(1, 0, n - 1);
		int u, v;
		rep (i, 1, n - 1) read(u, v), add_edge(u, v), add_edge(v, u);
		dfs1(1, 0), dfs2(1, 1);
		rep (i, 0, (int) f[1].size() - 1) {
			int d = (int) f[1].size() - i;
			ans += min(f[1][i].fir, seg_tree.query(1, 0, n - 1, d - f[1][i].sec, d - 1));
		}
		printf("%lld\n", ans);
	}
return 0;
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/