#include<bits/stdc++.h>
#define AC return 0;
#define int long long 
#define pii pair<int,int>
#define all(tar) tar.begin(),tar.end()
const int maxn=2e5+5;
const int mod=998244353; 
using namespace std;
int n,t;
int dfn[maxn],idx;
int h[maxn], m, a[maxn], len;  // 存储关键点
int anc[maxn][20];
int dep[maxn];
vector<int>G[maxn];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    anc[u][0]=fa;
    dfn[u]=++idx;
    for(int i=1;(1<<i)<=dep[u];i++){
        anc[u][i]=anc[anc[u][i-1]][i-1];
    }
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
}
void conn(int u,int v){
   G[u].push_back(v);
   G[v].push_back(u);
}
bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // 按照 dfs 序排序
}
int lca(int u,int v){
     if(dep[u]<dep[v])swap(u,v);
     int k=log2(dep[u]);
     for(int i=k;i>=0;i--){
        if(dep[anc[u][i]]>=dep[v])u=anc[u][i];
     }
     if(u==v)return u;
     k=log2(dep[u]);
     for(int i=k;i>=0;i--){
        if(anc[u][i]==anc[v][i])continue;
        u=anc[u][i];
        v=anc[v][i]; 
     }
     return anc[u][0];
}
void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // 把关键点按照 dfs 序排序 
  len=0;
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // 插入 lca
  }
 
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // 把所有虚树上的点按照 dfs 序排序
  len = unique(a + 1, a + len + 1) - a - 1;  // 去重
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // 连边，如有边权 就是 distance(lc,a[i+1])
  }
}
int dp_max[maxn][20], dp_min[maxn][20], LOG[maxn], val[maxn];
void ST(int n, int d[]) {
	LOG[0] = -1;
	for (int i = 1; i <= n; i++) {
		dp_min[i][0] = dp_max[i][0] = d[i];
		LOG[i] = LOG[i / 2] + 1;
	}
	for (int j = 1; (1 << j) <= n; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]);
			dp_min[i][j] = min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
		}
	}
}
int RMQ_max(int l, int r) {
	int k = LOG[r - l + 1];
	return max(dp_max[l][k], dp_max[r - (1 << k) + 1][k]);
}
int RMQ_min(int l, int r) {
	int k = LOG[r - l + 1];
	return min(dp_min[l][k], dp_min[r - (1 << k) + 1][k]);
}
int now;
vector<int>num[maxn];
int dp(int u,int fa){
    if(G[u].size()==1&&u!=1)return RMQ_min(1,now-dep[fa]+1);
    int ans=0;
    int x;
    if(u==1)x=val[now];
    else x=RMQ_min(now-dep[u]+1,now-dep[fa]+1);
    for(auto v:G[u]){
        if(v==fa)continue;
          ans+=dp(v,u);
    }
    // if(now==2)cout<<ans<<" "<<x<<'\n';
    return min(ans,x);
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin>>t;
   while(t--){
    cin>>n;
    for(int i=1;i<=n;i++){
      cin>>val[i];
      num[i].clear();
      G[i].clear();   
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    for(int i=2;i<=n;i++){
        num[dep[i]].push_back(i);
    }
    ST(n,val);
    int ans=val[1];
    for(int i=1;i<=n;i++)G[i].clear();
    for(int i=2;i<=n;i++){
        m=0;
        h[++m]=1;
       for(auto x:num[i])h[++m]=x;
       build_virtual_tree();
       now=i;
       ans+=dp(1,0);
    //    cout<<i<<'\n';
    //    for(int i=1;i<=len;i++)cout<<a[i]<<' ';
    //    cout<<ans<<'\n';
       for(int i=1;i<=len;i++)G[a[i]].clear();
    }
    cout<<ans<<'\n';   
   }
   AC
}