#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;

const int H = 17;

struct Update
{
	int pos, lef, rig;
};

vector <int> g[100005];
int cost[100005], metka[100005];
vector <ll> dp[100005];
vector <Update> updates[100005];
int sp[H + 3][100005], logs[100005];

int get_min(int lef, int rig)
{
 	int step = logs[rig - lef + 1];
 	return min(sp[step][lef], sp[step][rig - (1 << step) + 1]);
}

void actualize(int v, int len)
{
 	len = min(len, (int) dp[v].size());
 	//cout << "Len: " << len << '\n';
 	while (!updates[v].empty() && (int) dp[v].size() - updates[v].back().pos <= len)
 	{
 	 	Update upd = updates[v].back();
 	 	//cout << "AAAA: " << v << ' ' << upd.pos << ' ' << upd.lef << ' ' << upd.rig << '\n';
 	 	updates[v].pop_back();

 	 	int L = upd.lef - upd.pos, R = upd.rig - upd.pos;
 	 	dp[v][upd.pos] = min(dp[v][upd.pos], (ll) get_min(L, R));
 	 	upd.pos--;
 	 	if (upd.pos >= 0)
 	 	{
 	 	 	if (!updates[v].empty() && updates[v].back().pos == upd.pos) updates[v].back().rig = upd.rig;
 	 	 	else updates[v].pb(upd);
 	 	}
 	}
 	return;
}

void write(int v)
{
 	cout << "Write: " << v << '\n';
 	cout << "Metka = " << metka[v] << '\n';
 	cout << "DP: ";
 	for (ll x : dp[metka[v]]) cout << x << ' ';
 	cout << '\n';
 	for (const auto &[pos, lef, rig] : updates[metka[v]]) cout << pos << ' ' << lef << ' ' << rig << '\n';
 	cout << "-----------\n";
 	return;
}

void dfsik(int v, int pr)
{
 	metka[v] = v;
 	int mx1 = 0, mx2 = 0;
 	for (int u : g[v])
 	{
 	 	if (u == pr) continue;
 	 	dfsik(u, v);
 	 	if (mx1 == 0 || (int) dp[metka[mx1]].size() <= (int) dp[metka[u]].size()) mx2 = mx1, mx1 = u;
 	 	else if (mx2 == 0 || (int) dp[metka[mx2]].size() <= (int) dp[metka[u]].size()) mx2 = u;
 	}
 	
 	if (mx1 == 0)
 	{
 	 	dp[metka[v]].pb(cost[0]);
 	 	//write(v);
 	 	return;
 	}
 	
 	metka[v] = metka[mx1];
 	if (mx2 == 0)
 	{
 		dp[metka[v]].pb(cost[0]);
 		updates[metka[v]].pb({(int) dp[metka[v]].size() - 2, (int) dp[metka[v]].size() - 1, (int) dp[metka[v]].size() - 1});
 		//write(v);
 		return;	 	
 	}

 	int len = (int) dp[metka[mx2]].size();
 	for (int u : g[v])
 	{
 	 	if (u == pr) continue;
 	 	actualize(metka[u], len);
 	}

 	for (int u : g[v])
 	{
 	 	if (u == pr || u == mx1) continue;
 	 	for (int i = 0; i < (int) dp[metka[u]].size(); i++)
 	 		dp[metka[v]][i] += dp[metka[u]][i];
 	}
 	dp[metka[v]].pb(cost[0]);
 	updates[metka[v]].pb({(int) dp[metka[v]].size() - 2, (int) dp[metka[v]].size() - 1, (int) dp[metka[v]].size() - 1});
 	//write(v);
 	return;
}	

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);

 	int test;
 	cin >> test;
 	for (int rep = 1; rep <= test; rep++)
 	{
 	 	int n;
 	 	cin >> n;
 	 	for (int i = 0; i < n; i++) cin >> cost[i];

 	 	logs[1] = 0;
 	 	for (int i = 2; i <= n; i++) logs[i] = logs[i / 2] + 1;
 	 	for (int i = 0; i < n; i++) sp[0][i] = cost[i];
 	 	for (int step = 1; step <= H; step++)
 	 		for (int i = 0; i < n; i++)
 	 		{
 	 		 	if (i + (1 << (step - 1)) < n) sp[step][i] = min(sp[step - 1][i], sp[step - 1][i + (1 << (step - 1))]);
 	 		 	else sp[step][i] = sp[step - 1][i];
 	 		}

 	 	for (int i = 1; i <= n; i++) g[i].clear(), dp[i].clear(), updates[i].clear();

 	 	for (int i = 1; i < n; i++)
 	 	{
 	 	 	int u, v;
 	 	 	cin >> u >> v;
 	 	 	g[u].pb(v), g[v].pb(u);
 	 	}
 	 	dfsik(1, -1);
 	 	actualize(metka[1], n);

 	 	ll ans = 0;
 	 	for (ll x : dp[metka[1]]) ans += x;
 	 	cout << ans << '\n';
 	}

 	return 0;
}