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

struct ST{
    vector<vector<int>>r;
    ST(vector<int>a){
        int n=a.size()-1;
        r.assign(n+1,vector<int>(__lg(n+1),0ll));
        for(int i=1;i<=n;++i) r[i][0]=a[i];
        for(int i=1;(1<<i)<=n;++i){
            for(int j=1;j+(1<<i)-1<=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]);
    }
};

void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i) cin>>a[i];
    ST st(a);
    vector<vector<int>>e(n+1);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int>dep(n+1);
    vector<map<int,int>>f(n+1);
    auto dfs=[&](auto dfs,int u,int fa)->void{
        dep[u]=dep[fa]+1;
        for(auto v:e[u]){
            if(v==fa) continue;
            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[1];
        for(int i=dep[u]+1;i<=x+1;++i) f[u][i]=min(f[u][i],st.querymin(i-dep[u]+1,i));
    };
    dfs(dfs,1,0);
    int res=0;
    for(auto [x,y]:f[1]) res+=y;
    cout<<res<<"\n";
}

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