#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
typedef long long LL;
typedef unsigned long long ull;
int n, m, k;
const int N = 1e6 + 10, M = 1e6 + 10, mod = 45989, inf = 1e17;
int res, cnt;
int num[N];

int dfn[N], tt;
int dep[N], book[N];
int st[N][20], lg[N];
vector<int> vt[N];

int mi(int A, int B) {
	return A < B ? A : B;
}

pll mi(pll A, pll B) {
	return A.fi < B.fi ? A : B;
}

int quer(int l, int r) {
	int k = lg[r - l + 1];
	return mi(st[l][k], st[r - (1 << k) + 1][k]);
}

struct G1 {
	int h[N], e[N << 1], ne[N << 1], idx;
	int sta[N], tot, pos[N];
	pll stl[N][20];
	void ini() {
		for (int i = 1; i <= n; i++) h[i] = -1;
		idx = 0;
		tot = 0;
		tt = 0;
	}

	void add(int a, int b) {
		e[idx] = b, ne[idx] = h[a], h[a] = idx++;
	}

	void dfs(int id, int f) {
		sta[++tot] = id;
		pos[id] = tot;
		dfn[id] = ++tt;
		for (int i = h[id]; i != -1; i = ne[i]) {
			int j = e[i];
			if (j == f) continue;
			dep[j] = dep[id] + 1;
			dfs(j, id);
			sta[++tot] = id;
		}
	}

	void run() {
		dfs(1, -1);
		for (int i = 1; i <= tot; i++) stl[i][0] = {pos[sta[i]], sta[i]};
		for (int j = 1; j <= lg[tot]; j++) {
			for (int i = 1; i + (1 << j) - 1 <= tot; i++) {
				stl[i][j] = mi(stl[i][j - 1], stl[i + (1 << (j - 1))][j - 1]);
			}
		}
	}


	int lca(int a, int b) {
		int l = pos[a], r = pos[b];
		int k = lg[r - l + 1];
		return mi(stl[l][k], stl[r - (1 << k) + 1][k]).se;
	}
} g1;

bool cmp(const int &A, const int &B) {
	return dfn[A] < dfn[B];
}

struct G2 {
	int h[N], e[N << 1], ne[N << 1], idx;
	int sta[N], tot;

	void ini() {
		idx = 0;
		for (int i = 1; i <= n; i++) h[i] = -1;
	}
	void add(int a, int b) {
		e[idx] = b, ne[idx] = h[a], h[a] = idx++;
	}

	int dfs(int id, int f, int lay) {
		int ans = 0;
		int cnt = 0;
		for (int i = h[id]; i != -1; i = ne[i]) {
			int j = e[i];
			if (j == f) continue;
			cnt++;
			ans += mi(quer(lay - dep[j], lay - dep[id]), dfs(j, id, lay));
		}
		ans = mi(ans, st[lay - dep[id]][0]);
		return ans;
	}

	void run(int K) {
		sort(vt[K].begin(), vt[K].end(), cmp);
		tot = 0;
		sta[++tot] = 1;
		int sz = vt[K].size();
		for (int i = 0; i < sz; i++) {
			int u = vt[K][i], p = g1.lca(sta[tot], u);
			if (u == 1) continue;
			if (p != sta[tot]) {
				while (tot >= 2 && dep[sta[tot - 1]] >= dep[p]) {
					add(sta[tot - 1], sta[tot]);
					tot--;
				}
				if (p != sta[tot]) {
					add(p, sta[tot]);
					sta[tot] = p;
					vt[K].push_back(p);
				}
			}
			sta[++tot] = u;
		}
		for (int i = 1; i < tot; i++) add(sta[i], sta[i + 1]);
		res += dfs(1, -1, K);
		h[1] = -1;
		for (auto it : vt[K]) h[it] = -1;
		idx = 0;
	}

} g2;

void ini() {
	lg[0] = -1;
	for (int i = 1; i <= M; i++) {
		if ((i & (i - 1)) == 0) lg[i] = lg[i - 1] + 1;
		else lg[i] = lg[i - 1];
	}
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> st[i][0];
	for (int j = 1; j <= lg[n]; j++) {
		for (int i = 0; i + (1 << j) - 1 <= n; i++) {
			st[i][j] = mi(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	g1.ini();
	g2.ini();
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g1.add(a, b);
		g1.add(b, a);
	}
	g1.run();
	for (int i = 1; i <= n; i++) vt[i].clear();
	for (int i = 1; i <= n; i++) vt[dep[i]].push_back(i);
	res = 0;
	for (int i = 1; i <= n; i++) g2.run(i);
	cout << res << endl;
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	ini();
	cin >> T;
	while (T--)solve();
	return 0;
}
/*
9
0 0 0 0 0 -1 -1 -1 -1
*/