#include <bits/stdc++.h>
using namespace std;
#define clo 1000.*clock()/CLOCKS_PER_SEC
#ifndef xxzx
#define endl '\n'
#endif
using ll=long long;
using PII=pair<int,int>;
const int N=1e5+10;
bool memory1;
int n,a[N],mn[N][20],Log[N];
vector<int> eg[N];
int GetMin(int l,int r) {
    int len=Log[r-l+1];
    return min(mn[l][len],mn[r-(1<<len)+1][len]);
}
int fa[N][20],dep[N],dfn[N],tim;
vector<int> nd[N];
void dfs(int x,int from) {
    fa[x][0]=from,dep[x]=dep[from]+1,nd[dep[x]].push_back(x),dfn[x]=++tim;
    for(auto y:eg[x]) if(y!=from) dfs(y,x);
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    for(int h=dep[x]-dep[y],i=0;h;h>>=1,i++)
        if(h&1) x=fa[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--)
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int vc[N];
ll f[N];
vector<int> g[N];
void dfs1(int x,int from,int D) {
    // D-[dep[fa[x]]+1,dep[x]]
    f[x]=GetMin(D-dep[x],D-(dep[from]+1));
    if(g[x].size())  {
        ll res=0;
        for(auto y:g[x]) res+=f[y];
        f[x]=min(f[x],res);
    }
}
ll ans;
void sol(vector<int> &nd,int D) {
    sort(nd.begin(),nd.end(),[](const int &x,const int &y){ return dfn[x]<dfn[y]; });
    int sz=nd.size(),m=0;
    for(auto i:nd) vc[++m]=i;
    for(int i=0;i+1<sz;i++) vc[++m]=lca(nd[i],nd[i+1]);

    sort(vc+1,vc+m+1,[](const int &x,const int &y){ return dfn[x]<dfn[y]; });
    m=unique(vc+1,vc+m+1)-vc-1;

    for(int i=1;i<=m;i++) g[vc[i]].clear(),f[vc[i]]=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i+1<=m;i++) g[lca(vc[i],vc[i+1])].push_back(vc[i+1]);

    dfs1(vc[1],0,D);
    ans+=f[vc[1]];

    // cerr<<"D "<<D<<" "<<f[vc[1]]<<" "<<GetMin(0,1)<<" "<<mn[1][0]<<endl;
}
void solve() {
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i],mn[i][0]=a[i];
    for(int j=1;j<20;j++) for(int i=0;i+(1<<j)-1<n;i++)
        mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
    for(int i=1;i<=n;i++) eg[i].clear(),nd[i].clear();
    for(int i=1,x,y;i<n;i++) {
        cin>>x>>y;
        eg[x].push_back(y),eg[y].push_back(x);
    }
    tim=0;
    dfs(1,0);
    for(int j=1;j<20;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
    ans=0;
    for(int d=1;d<=n;d++) if(nd[d].size()) sol(nd[d],d);
    cout<<ans<<endl;
}
bool memory2;
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    for(int i=2;i<N;i++) Log[i]=Log[i>>1]+1;
    int _; cin>>_;
    while(_--) solve();

    #ifdef xxzx
    cerr<<"Time: "<<clo<<"MS"<<endl;
    cerr<<"Memory: "<<abs(&memory1-&memory2)/1024./1024.<<"MB"<<endl;
    #endif
    return 0;
}