#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
vector<int> adj[MAX], nodes_in_depth[MAX], mono_ton;
int arr[MAX], dp[MAX], anc[20][MAX], lvl[MAX], st[MAX], T, ed[MAX];
void dfs(int u,int par = 0){
	anc[0][u] = par, lvl[u] = lvl[par] + 1, nodes_in_depth[lvl[u]].push_back(u), st[u] = T++;
	for(int j = 1; j < 20; j++) anc[j][u] = anc[j - 1][anc[j - 1][u]];
	for(auto v : adj[u]){
		if(v == par) continue;
		dfs(v, u);
	}
	ed[u] = T;
}

int lca(int u,int v){
	if(lvl[u] < lvl[v]) swap(u, v);
	for(int j = 19; j >= 0; j--) if(lvl[u] - (1 << j) >= lvl[v]) u = anc[j][u];
	if(u == v) return u;
	for(int j = 19; j >= 0; j--) if(anc[j][u] != anc[j][v]) u = anc[j][u], v = anc[j][v];
	return anc[0][u];
}

int is_a_ancestor_of_b(int a,int b){
	return st[a] <= st[b] && st[b] < ed[a];
}
int f(int u,int dpth){
	if(!adj[u].size()) return arr[*lower_bound(mono_ton.begin(), mono_ton.end(), dpth - lvl[u])];
	long long ret = 0;
	for(auto v : adj[u]){
		ret += f(v, dpth);
	}

	return min((long long)arr[*lower_bound(mono_ton.begin(), mono_ton.end(), dpth - lvl[u])], ret);
}
int yo(vector<int> v,int dpth){
	if(v.size() == 0) return 0;
	int sz = v.size();
	for(int i = 1; i < sz; i++) v.push_back(lca(v[i], v[i - 1]));
	sort(v.begin(), v.end(), [&](int a, int b){ return st[a] < st[b];});
	for(auto x : v) adj[x].clear();
	stack<int> stk;
	stk.push(v[0]);
	for(int i = 1; i < v.size(); i++){
		while(!is_a_ancestor_of_b(stk.top(), v[i])) stk.pop();
		adj[stk.top()].push_back(v[i]);
		stk.push(v[i]);
	}
	return f(v[0], dpth);
}

void solve(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> arr[i], adj[i + 1].clear(), nodes_in_depth[i + 1].clear();
	mono_ton.clear();
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y), adj[y].push_back(x);
	}
	dfs(1);
	long long ans = 0;
	mono_ton.push_back(0);
	for(int i = 1; i <= n; i++){
		ans += yo(nodes_in_depth[i], i);
		while(mono_ton.size() && arr[mono_ton.back()] > arr[i]) mono_ton.pop_back();
		mono_ton.push_back(i);
	}
	cout << ans << '\n';
}

int32_t main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--) solve();
}