#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
#include<deque>
using namespace std;

#define MAXN 201000
#define ll long long
#define lll unsigned long long
#define PA pair<ll,ll>
#define INF (ll)0x3f3f3f3f*(ll)1000000
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const ll mod = 1e9+7;


struct node {
	int from, next, to;
}edge[MAXN * 2];
int head[MAXN], id;

void add(int x, int y) {
	edge[++id].next = head[x];
	edge[id].from = x;
	edge[id].to = y;
	head[x] = id;
}

int n;
int times;
vector<int>arr;

ll stmin[MAXN][32];
int log_2[MAXN];

int depth[MAXN];//每一个点的深度
int dfn[MAXN];//每个点的dfs序
int fa[MAXN][32];
vector<vector<int>>dpnode;//每个深度的点门
int madepth;//最大深度

int a[MAXN];

void dfs(int now, int last) {

	int len = depth[last] + 1;
	madepth = max(madepth, len);
	depth[now] = len;

	fa[now][0] = last;

	dpnode[len].push_back(now);

	dfn[now] = ++times;

	for (int i = head[now]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == last)continue;

		dfs(v, now);
	}
}

void swimup(int& x, int c) {
	for (int i = 0; (1 << i) <= c ; i++)
		if ((c) & (1 << i)) x = fa[x][i];
}

int getlca(int x, int y) {
	if (depth[x] < depth[y]) {
		swap(x, y);
	}

	int c = depth[x] - depth[y];
	swimup(x, c);

	if (x == y) {
		return x;
	}
	for (int i = 30; i >= 0; i--)
	{
		if (fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}

	return fa[x][0];
}

ll dp[MAXN];
ll DP(int now, int last, int D) {

	bool c = false;
	dp[now] = 0;

	ll sum = 0;
	for (int i = head[now]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == last)continue;

		ll ad = DP(v, now, D);
		c = true;
		sum += ad;
	}

	if (!c) {
		int l, r;
		r = D - (depth[last] + 1);
		l = D - depth[now];
		int x = log_2[r - l + 1];
		dp[now] = min(min(stmin[l][x], stmin[r - (1 << x) + 1][x]), (ll)arr[0]);
	}
	else {
		int l, r;
		r = D - (depth[last] + 1);
		l = D - depth[now];
		int x = log_2[r - l + 1];
		dp[now] = min(min(stmin[l][x], stmin[r - (1 << x) + 1][x]), sum);
	}

	return dp[now];
}

void init() {
	arr.clear(); arr.resize(n);
	madepth = 0;
	memset(head, 0, sizeof head);
	dpnode.clear(); dpnode.resize(n + 1);
}

void solve() {
	cin >> n;
	init();
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y;
		add(x, y); add(y, x);
	}

	log_2[0] = -1;
	for (int i = 1; i <= n; i++) {
		log_2[i] = log_2[i >> 1] + 1;
	}

	for (int i = 0; i < n; i++)stmin[i][0] = arr[i];
	for(int j=1;j<21;j++)
		for (int i = 0; i + (1 << j) - 1 <= n; i++) {
			stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << j) - 1][j - 1]);
		}

	dfs(1, 0);

	for (int j = 1; j <= 30; j++) {
		for (int i = 1; i <= n; i++) {
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}

	ll ans = 0;
	memset(head, 0, sizeof head); id = 0;
	for (int i = madepth; i >= 1; i--) {

		memset(head, 0, sizeof head); id = 0;
		auto nodes = dpnode[i];
		nodes.push_back(1);
		sort(nodes.begin(), nodes.end(), [](const int& w, const int& b) {
			return dfn[w] < dfn[b];
			});

		int l = 0;
		for (int j = 0; j < nodes.size() - 1; j++) {
			a[++l] = nodes[j];
			a[++l] = getlca(nodes[j], nodes[j + 1]);
		}
		a[++l] = nodes.back();

		sort(a + 1, a + l + 1, [](const int& w, const int& b) {
			return dfn[w] < dfn[b];
			});
		l = unique(a + 1, a + l + 1) - a - 1;


		for (int j = 1; j < l; j++) {
			int lc = getlca(a[j], a[j + 1]);
			add(lc, a[j + 1]);
			//add(a[j + 1], lc);
		}
		//以上建树完毕

		ans += DP(1, 0, i);

	}

	cout << ans<<endl;
}
int main() {
	IOS;
	int t = 1; cin >> t;
	while (t--) {
		solve();
	}
}