#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,S=21;
vector<vector<int>> e,leaf,fa,mi,pos;
vector<int> a,dep,dfn,_2;
int tot;
int n;
int query(int l,int r)
{
	l++; r++;
	int len=r-l+1;
	int t=_2[len];
	return min(mi[l][t],mi[r-(1<<t)+1][t]);
}
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
void dfs1(int u)
{
	dep[u]=dep[fa[u][0]]+1;
	leaf[dep[u]].push_back(u);
	dfn[u]=++tot;
	for(auto v:e[u])
	{
		if(v==fa[u][0]) continue;
		fa[v][0]=u;
		dfs1(v);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=S-1; i>=0; i--)
	{
		if(dep[fa[x][0]]>=dep[y])
			x=fa[x][0];
	}
	if(x==y) return x;
	for(int i=S-1; i>=0; i--)
	{
		if(fa[x][0]!=fa[y][0])
		{
			x=fa[x][0];
			y=fa[y][0];
		}
	}
	return fa[x][0];
}
//vector<int> dp;
int dfs2(int u,int fa,int d)
{
	if(dep[u]==d)
	{
		return query(0,d-1);
	}
	int res=0;
	for(auto v:e[u])
	{
		if(v==fa) continue;
		res+=dfs2(v,u,d);
	}
	return min(res,query(d-dep[u],d-dep[fa]-1));
}
int solve(int id)
{
	sort(leaf[id].begin(),leaf[id].end(),cmp);
	int n=leaf[id].size();
	for(int i=0; i<n-1; i++)
	{
		leaf[id].push_back(lca(leaf[id][i],leaf[id][i+1]));
	}
	sort(leaf[id].begin(),leaf[id].end(),cmp);
	leaf[id].erase(unique(leaf[id].begin(),leaf[id].end()),leaf[id].end());
	n=leaf[id].size();
	for(int i=0; i<n-1; i++)
	{
		int l=lca(leaf[id][i],leaf[id][i+1]);
		e[leaf[id][i+1]].push_back(l);
		e[l].push_back(leaf[id][i+1]);
	}
	int res=dfs2(1,0,id);
	for(auto x:leaf[id])
		e[x].clear();
	return res;
}
void O_o()
{
	cin>>n;
	pos.assign(n+2,vector<int>(S,0));
	mi.assign(n+2,vector<int>(S,inf));
	_2.assign(n+2,0);
	e.assign(n+1,vector<int>());
	fa.assign(n+1,vector<int>(S,0));
	leaf.assign(n+1,vector<int>());
	a.assign(n+1,0);
	_2[0]=-1;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		mi[i][0]=a[i];
		pos[i][0]=i+1;
		_2[i]=_2[i>>1]+1;
	}
	for(int j=1; j<S; j++)
	{
		for(int i=1; i<=n; i++)
		{
			pos[i][j]=pos[pos[i][j-1]][j-1];
			mi[i][j]=min(mi[i][j-1],mi[pos[i][j-1]][j-1]);
		}
	}
	for(int i=1; i<n; i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dep.assign(n+1,0);
	dfn.assign(n+1,0);
	tot=0;
	dfs1(1);
	for(int j=1; j<S; j++)
	{
		for(int i=1; i<=n; i++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	int ans=0;
	e.assign(n+1,vector<int>());
	for(int i=1; i<=n; i++)
	{
		if(i!=1)
			leaf[i].push_back(1);
		ans+=solve(i);
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout<<fixed<<setprecision(12);
	int T=1;
	cin>>T;
	while(T--)
	{
		O_o();
	}
}