#include <bits/stdc++.h>
using namespace std;
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i < b;i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x.size())
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
#define fi first
#define se second
const int MAXN =3e5+5;
vector<vi>adj,g(MAXN);
vector<ll>a;
vector<int>depth;
template<class T>
struct RMQ{
	vector<vector<T>> jmp;
	RMQ(){}
	RMQ(const vector<T>&V):jmp(1,V){
		for(int pw=1,k=1;pw *2 <= sz(V); pw*=2, ++k){
			jmp.emplace_back(sz(V) - pw*2 + 1);
			rep(j,0,sz(jmp[k])){
				jmp[k][j] = min(jmp[k-1][j],jmp[k-1][j+pw]);
			}
			
		}
	}
	T query(int a,int b){
		assert(a < b);
		int dep = 31 - __builtin_clz(b-a);
		return min(jmp[dep][a],jmp[dep][b-(1<<dep)]);
	}
};
RMQ<ll> drmq;

struct LCA{
	int T = 0;
	vi time,path,ret;
	RMQ<int> rmq;
	
	LCA(vector<vi>& C): time(sz(C)), rmq((dfs(C,0,-1),ret)) {}
	void dfs(vector<vi>&C,int v,int par){
		time[v] = T++;
		for(int y:C[v]){
			if(y != par){
				depth[y] = depth[v] + 1;
				path.push_back(v);
				ret.push_back(time[v]);
				dfs(C,y,v);
			}
		}
	}
	
	int lca(int a,int b){
		if(a==b)return a;
		tie(a,b) = minmax(time[a],time[b]);
		return path[rmq.query(a,b)];
	}
};

typedef vector<pair<int,int>> vpi;
vpi compressTree(LCA& lca,const vi& subset){
	static vi rev;rev.resize(sz(lca.time));
	vi li = subset, &T = lca.time;
	
	auto cmp = [&](int a,int b){return T[a] < T[b];};
	li.push_back(0);
	sort(all(li),cmp);
	int m = sz(li)-1;
	rep(i,0,m){
		int a = li[i], b = li[i+1];
		li.push_back(lca.lca(a,b));
	}
	sort(all(li),cmp);
	li.resize(unique(all(li)) - li.begin());
	rep(i,0,sz(li))rev[li[i]] = i;
	//for(int x:li)cout<<x<<" ";
	//cout<<'\n';
	vpi ret;
	rep(i,0,sz(li)-1){
		int a = li[i],b = li[i+1];
		ret.emplace_back(lca.lca(a,b),b);
	}
	return ret;
}
ll dp[MAXN];
void dfs2(int v,int dep){
	if(g[v].empty()){
		dp[v] = a[0];
		return;
	}
	dp[v] = 0;
	for(int x:g[v]){
		dfs2(x,dep);
		int len = depth[x] - depth[v];
		ll s = dp[x];
		if(len>1)s = min(s,drmq.query(dep-depth[x],dep-depth[v]));
		
		dp[v] += s;
	}
	//cout<<v<<" "<<dp[v]<<'\n';
	dp[v] = min(dp[v],a[dep-depth[v]]);
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		a.resize(n);
		adj.resize(n);
		depth.assign(n,0);
		for(int i=0;i<n;i++){
			cin>>a[i];
			adj[i].clear();
			g[i].clear();
		}
		drmq = RMQ<ll>(a);
		for(int i=1;i<n;i++){
			int u,v;
			cin>>u>>v;
			u--;v--;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		LCA lca(adj);
		vector<vi>dd(n);
		for(int i=0;i<n;i++)dd[depth[i]].push_back(i);
		ll ans = 0;
		for(int i=0;i<n;i++){
			if(dd[i].empty())continue;
			//cout<<"depth "<<i<<'\n';
			//for(int x:dd[i])cout<<x<<" ";
			//cout<<'\n';
			vpi ret = compressTree(lca,dd[i]);
			for(auto x:ret){
				g[x.fi].clear();
				dp[x.fi] = 1e18;
			}
			for(auto x:ret)g[x.fi].push_back(x.se);
			dfs2(0,i);
			//for(int j=0;j<n;j++)cout<<dp[j]<<" ";
			//cout<<'\n';
			ans += dp[0];
		}
		cout<<ans<<'\n';
	}
	
	
	
}