#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int>G[100010];
int n,mi[100010][25],mxdis[100010],dfn[100010],las[100010],tot;
ll f[100010];
auto query=[](int l,int r){int g=__lg(r-l+1);return min(mi[l][g],mi[r-(1<<g)+1][g]);};
void dfs(int u,int fa){
    if(fa)G[u].erase(find(begin(G[u]),end(G[u]),fa));
    for(int&v:G[u]){
        dfs(v,u);
        if(mxdis[v]+1>mxdis[u])
         mxdis[u]=mxdis[v]+1,swap(v,G[u][0]);
    }
}
auto upd=[](int ind,int now){if(las[ind]<=now)f[ind]=min(f[ind],(ll)query(las[ind],now)),las[ind]=now+1;return f[ind];};
void solve(int u){
    dfn[u]=++tot;
    for(int v:G[u]){
        solve(v);
        if(v!=G[u][0])
        for(int i=0;i<=mxdis[v];i++){
            upd(dfn[u]+i+1,i);
            f[dfn[u]+i+1]+=upd(dfn[v]+i,i);
        }
    }
}
int main(){
    int T;for(cin>>T;T--;){
        cin>>n;
        for(int i=1;i<=n;i++)dfn[i]=mxdis[i]=las[i]=0,f[i]=1e18,G[i].clear();
        for(int i=0;i<n;i++)scanf("%d",&mi[i][0]);
        for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
        for(int i=1;i<=20;i++)
        for(int j=0;j+(1<<i)<=n;j++)
        mi[j][i]=min(mi[j][i-1],mi[j+(1<<i-1)][i-1]);
        dfs(1,0),solve(1);
        ll ans=0;
        for(int i=0;i<=mxdis[1];i++)ans+=upd(i+1,i);
        cout<<ans<<endl;
    }
    return 0;
}