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

struct ST{
    vector<vector<int>>r;
    void build(vector<int>a){
        int n=a.size();
        r.assign(n,vector<int>(__lg(n),0ll));
        for(int i=0;i<n;++i) r[i][0]=a[i];
        for(int i=1;(1<<i)<=n;++i){
            for(int j=0;j+(1<<i)<=n;++j){
                r[j][i]=min(r[j][i-1],r[j+(1<<i-1)][i-1]);
            }
        }
    }
    int querymin(int x,int y){
        int t=__lg(y-x+1);
        return min(r[x][t],r[y-(1<<t)+1][t]);
    }
}st;
map<int,int>f[100008];

void solve(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    st.build(a);
    vector<vector<int>>e(n);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        --u,--v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int>dep(n);
    auto dfs=[&](auto dfs,int u,int fa)->void{
        f[u].clear();
        for(auto v:e[u]){
            if(v==fa) continue;
            dep[v]=dep[u]+1;
            dfs(dfs,v,u);
            if(f[u].size()<f[v].size()) swap(f[u],f[v]);
            for(auto [x,y]:f[v]) f[u][x]+=y;
        }
        int x=dep[u];
        for(auto v:e[u]){
            if(v==fa) continue;
            if(f[v].size()) x=max(x,(*f[v].rbegin()).first);
        }
        f[u][dep[u]]=a[0];
        for(int i=dep[u]+1;i<=x+1;++i) f[u][i]=min(f[u][i],st.querymin(i-dep[u],i));
    };
    dfs(dfs,0,-1);
    int res=0;
    for(auto [x,y]:f[0]) res+=y;
    cout<<res<<"\n";
}

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