// Hydro submission #678f0d383e10c2b5101f086e@1737428281061
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, dfncnt, rt;
int a[N], dfn[N], dep[N], lg2[N], fa[N][18];
long long dp[N], stc[N][18];
vector<int> g[N], h[N], vtp, vt[N], imp;

void init(){
	dfncnt = 0;
	vtp.clear();
	for(int i = 0; i <= n; i++){
		g[i].clear(), h[i].clear(), vt[i].clear();
		dep[i] = dfn[i] = dp[i] = a[i] = 0;
		for(int j = 0; j < 18; j++) {
			stc[i][j] = 1e18;
			fa[i][j] = 0;
		}
	}
	n = rt = 0;
	return ;
}

inline long long query_min(int l, int r){
	l++, r++;
	int T = lg2[r - l + 1];
	return min(stc[l][T], stc[r - (1 << T) + 1][T]);
}

void dfs(int u, int pre){
	dfn[u] = ++dfncnt;
	dep[u] = dep[pre] + 1; h[dep[u]].push_back(u);
	fa[u][0] = pre; for(int i = 1; i <= 20; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(int v : g[u]) if(v != pre)
		dfs(v, u);
	return ;
}
inline int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 17; i >= 0; i--)
		if(dep[fa[x][i]] >= dep[y])
			x = fa[x][i];
	if(x == y) return x;
	for(int i = 17; i >= 0; i--)
		if(fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline void build_virtual_tree(){
	sort(imp.begin(), imp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
	vtp.clear();
	for(int i = 0; i < imp.size() - 1; i++)
		vtp.push_back(imp[i]), vtp.push_back(lca(imp[i], imp[i + 1]));
	vtp.push_back(imp.back());
	sort(vtp.begin(), vtp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
	int len = unique(vtp.begin(), vtp.end()) - vtp.begin();
	for(int i : vtp) vt[i].clear();
	for(int i = 0, lc; i < vtp.size() - 1; i++){
		lc = lca(vtp[i], vtp[i + 1]);
		vt[lc].push_back(vtp[i + 1]);
	}
	rt = vtp[0];
	return ;
}

void dfs_on_vt(int u, int pre, int D){
	dp[u] = (!vt[u].size()) * 1e18;
	for(int v : vt[u]){
		dfs_on_vt(v, u, D);
		dp[u] += dp[v];
	}
	dp[u] = min(dp[u], query_min(D - dep[u], D - dep[pre] - 1));
	return ;
}

void work(){
	init();

	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], stc[i][0] = a[i];
	for(int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
	for(int i = 1; i <= 17; i++)
		for(int j = 1; j + (1 << i) - 1 <= n; j++)
			stc[j][i] = min(stc[j][i - 1], stc[j + (1 << (i - 1))][i - 1]);

	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);

	long long ans = 0;
	for(int i = 1; i <= n; i++) if(h[i].size()){
		imp = h[i];
		build_virtual_tree();
		dfs_on_vt(rt, 0, i);
		ans += dp[rt];
	}
	cout << ans << "\n";
	return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T--) work();
	return 0;
}

answer.code: In function ‘void dfs(int, int)’:
answer.code:37:21: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
   37 |         for(int v : g[u]) if(v != pre)
      |                     ^
answer.code:37:24: error: forming reference to reference type ‘std::vector<int>&’
   37 |         for(int v : g[u]) if(v != pre)
      |                        ^
answer.code: In function ‘void build_virtual_tree()’:
answer.code:53:82: warning: lambda expressions only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
   53 |         sort(imp.begin(), imp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
      |                                                                                  ^
answer.code:53:13: error: no matching function for call to ‘sort(std::vector<int>::iterator, std::vector<int>::iterator, build_virtual_tree()::<lambda(int, int)>)’
   53 |         sort(imp.begin(), imp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/14/bits/stl_algo.h:4761:5: note: candidate: ‘template<class _RAIter> void std::sort(_RAIter, _RAIter)’
 4761 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~
/usr/include/c++/14/bits/stl_algo.h:4761:5: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/stl_algo.h:4792:5: note: candidate: ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)’
 4792 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
/usr/include/c++/14/bits/stl_algo.h:4792:5: note:   template argument deduction/substitution failed:
answer.code: In substitution of ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = build_virtual_tree()::<lambda(int, int)>]’:
answer.code:53:6:   required from here
   53 |         sort(imp.begin(), imp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:53:13: error: template argument for ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)’ uses local type ‘build_virtual_tree()::<lambda(int, int)>’
answer.code:53:13: error:   trying to instantiate ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)’
answer.code:58:82: warning: lambda expressions only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
   58 |         sort(vtp.begin(), vtp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
      |                                                                                  ^
answer.code:58:13: error: no matching function for call to ‘sort(std::vector<int>::iterator, std::vector<int>::iterator, build_virtual_tree()::<lambda(int, int)>)’
   58 |         sort(vtp.begin(), vtp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4761:5: note: candidate: ‘template<class _RAIter> void std::sort(_RAIter, _RAIter)’
 4761 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~
/usr/include/c++/14/bits/stl_algo.h:4761:5: note:   candidate expects 2 arguments, 3 provided
/usr/include/c++/14/bits/stl_algo.h:4792:5: note: candidate: ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)’
 4792 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
/usr/include/c++/14/bits/stl_algo.h:4792:5: note:   template argument deduction/substitution failed:
answer.code: In substitution of ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = build_virtual_tree()::<lambda(int, int)>]’:
answer.code:58:6:   required from here
   58 |         sort(vtp.begin(), vtp.end(), [](int _x, int _y){return dfn[_x] < dfn[_y];});
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:58:13: error: template argument for ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)’ uses local type ‘build_virtual_tree()::<lambda(int, int)>’
answer.code:58:13: error:   trying to instantiate ‘template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)’
answer.code:60:21: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
   60 |         for(int i : vtp) vt[i].clear();
  ...