#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 INF = 1e10;

struct HLD
{
	int n;
	std::vector<int> siz, top, dep, fa, L, R, id;
	std::vector<std::vector<int>> adj;
	int cur;

	HLD() {}
	HLD(int n)
	{
		init(n);
	}

	void init(int n)
	{
		this->n = n;
		siz.resize(n);
		top.resize(n);
		dep.resize(n);
		fa.resize(n);
		L.resize(n);
		R.resize(n);
		id.resize(n);

		cur = 0;
		adj.assign(n, {});
	}

	void add(int u, int v)
	{
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}

	void work(int root = 0)
	{
		top[root] = root;
		dep[root] = 0;
		fa[root] = -1;
		dfs1(root);
		dfs2(root);
	}

	void dfs1(int x)
	{
		if(fa[x] != -1)
			adj[x].erase(std::find(adj[x].begin(), adj[x].end(), fa[x]));

		siz[x] = 1;
		for(auto &y : adj[x])
		{
			fa[y] = x;
			dep[y] = dep[x] + 1;
			dfs1(y);

			siz[x] += siz[y];
			if(siz[y] > siz[adj[x][0]]) std::swap(y, adj[x][0]);
		}
	}

	void dfs2(int x)
	{
		L[x] = cur++;
		id[L[x]] = x;

		for(auto y : adj[x])
		{
			top[y] = (y == adj[x][0] ? top[x] : y);
			dfs2(y);
		}
		R[x] = cur;
	}

	int lca(int x, int y)
	{
		while(top[x] != top[y])
		{
			if(dep[top[x]] > dep[top[y]]) x = fa[top[x]];
			else y = fa[top[y]];
		}

		return dep[x] < dep[y] ? x : y;
	}
};

struct ST
{
	std::vector<std::vector<int>> f;

	ST(std::vector<int> &a)
	{
		int n = a.size(), logn = std::__lg(n);
		f.assign(n, std::vector<int>(logn + 1));

		for(int i = 0; i < n; i++) f[i][0] = a[i];
		for(int j = 0; j < logn; j++)
			for(int i = 0; i + (1 << (j + 1)) - 1 < n; i++)
				f[i][j + 1] = std::min(f[i][j], f[i + (1 << j)][j]);
	}

	int operator()(int l, int r)
	{
		if(l == r) return 0;
		int log = std::__lg(r - l);
		return std::min(f[l][log], f[r - (1 << log)][log]);
	}
};

void solve()
{
	int n; std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++) std::cin >> a[i];
	ST st(a);

	HLD tr(n);
	for(int i = 1; i < n; i++)
	{
		int u, v; std::cin >> u >> v;
		u--, v--;
		tr.add(u, v);
	}
	tr.work();

	std::vector<std::vector<int>> vec(n);
	for(int i = 0; i < n; i++) 
		vec[tr.dep[i]].emplace_back(i);

	// std::vector<std::vector<int>> adj(n);
	auto cacl = [&](int D) -> i64
	{
		std::vector<std::vector<int>> adj(n);
		if(D) vec[D].emplace_back(0);
		std::sort(vec[D].begin(), vec[D].end(), [&](int x, int y)
			{
				return tr.L[x] < tr.L[y];
			});

		std::vector<int> tmp;
		for(int i = 0; i + 1 < (int)vec[D].size(); i++)
		{
			tmp.emplace_back(vec[D][i]);
			tmp.emplace_back(tr.lca(vec[D][i], vec[D][i + 1]));
		}
		tmp.emplace_back(vec[D].back());
		std::sort(tmp.begin(), tmp.end(), [&](int x, int y)
			{
				return tr.L[x] < tr.L[y];
			});
		tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());

		for(int i = 1; i < (int)tmp.size(); i++)
		{
			int lca = tr.lca(tmp[i], tmp[i - 1]);
			adj[lca].emplace_back(tmp[i]);
		}

		auto dfs = [&](auto dfs, int x, int fa) -> i64
		{
			i64 res = 0;
			if(adj[x].empty()) res = INF;
			else for(auto y : adj[x])
				res += dfs(dfs, y, x);

			if(fa != -1) res = std::min<i64>(res, st(D - tr.dep[x], D - tr.dep[fa] + 1));

			return res;
		};
		return dfs(dfs, 0, -1);
	};

	i64 ans = a[0];
	for(int i = 1; i < n; i++) if(vec[i].size()) 
		ans += cacl(i);

	std::cout << ans << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; std::cin >> t;
	while(t--) solve();

	return 0;
}