/*你说的对，但是大样例呢*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#define int long long
using namespace std;
int n,a[100010];
struct ST{
    int st[100010][21];
    void build(){
        for(int i=0;i<n;i++)st[i][0]=a[i];
        for(int j=1;j<=__lg(n);j++){
            for(int i=0;i+(1<<j)-1<n;i++){
                st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
            }
        }
    }
    int query(int l,int r){
        if(l>r){
            cerr<<l<<r;
            assert(l<=r);
        }
        int k=__lg(r-l+1);
        return min(st[l][k],st[r-(1<<k)+1][k]);
    }
}st;
struct node{
    int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
    edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int dep[100010],son[100010],sec[100010];
void dfs1(int x,int f){
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f){
            dfs1(edge[i].v,x);
            if(dep[son[x]]<dep[edge[i].v])sec[x]=dep[son[x]],son[x]=edge[i].v;
            else if(sec[x]<dep[edge[i].v]+1)sec[x]=dep[edge[i].v]+1;
        }
    }
    dep[x]=dep[son[x]]+1;
}
int buf1[100010],*dp[100010],*now1=buf1;
int buf2[100010],*lz[100010],*now2=buf2;
void dfs2(int x,int f){
    if(son[x]){
        dp[son[x]]=dp[x]+1;lz[son[x]]=lz[x]+1;
        dfs2(son[x],x);
    }
    dp[x][0]=a[0];
    for(int i=0;i<sec[x];i++)dp[x][i]=min(dp[x][i],st.query(lz[x][i],i));
    for(int i=head[x];i;i=edge[i].next){
        if(edge[i].v!=f&&edge[i].v!=son[x]){
            dp[edge[i].v]=now1;now1+=dep[edge[i].v];
            lz[edge[i].v]=now2;now2+=dep[edge[i].v];
            dfs2(edge[i].v,x);
            for(int j=1;j<=dep[edge[i].v];j++){
                dp[edge[i].v][j-1]=min(dp[edge[i].v][j-1],st.query(lz[edge[i].v][j-1],j));
                dp[x][j]+=dp[edge[i].v][j-1];
            }
        }
    }
    for(int i=0;i<sec[x];i++)lz[x][i]=i;
}
void clear(){
    t=0;
    for(int i=1;i<=n;i++)head[i]=son[i]=dep[i]=sec[i]=buf1[i]=buf2[i]=0;
    now1=buf1;now2=buf2;
}
signed main(){
    // freopen("color.in","r",stdin);
    // freopen("color.out","w",stdout);
    int tim=1;
    scanf("%lld",&tim);
    while(tim--){
        scanf("%lld",&n);
        for(int i=0;i<n;i++)scanf("%lld",&a[i]);
        st.build();
        for(int i=1;i<n;i++){
            int u,v;scanf("%lld%lld",&u,&v);
            add(u,v);add(v,u);
        }
        dfs1(1,0);
        dp[1]=now1;now1+=dep[1];lz[1]=now2;now2+=dep[1];
        dfs2(1,0);
        int ans=0;
        for(int i=0;i<dep[1];i++){
            dp[1][i]=min(dp[1][i],st.query(lz[1][i],i));
            ans+=dp[1][i];
        }
        printf("%lld\n",ans);
        clear();
    }
    return 0;
}