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

typedef long long ll;
const int maxn=1e5+10;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(x=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int t;
int n;
int a[maxn];
int stmn[maxn][18];
inline void build(){
    for(int i=0;i<n;++i) stmn[i][0]=a[i];
    for(int k=1;k<=17;++k){
        for(int i=0;i+(1<<k)-1<n;++i){
            stmn[i][k]=min(stmn[i][k-1],stmn[i+(1<<k-1)][k-1]);
        }
    }
}
inline int query(int l,int r){
    assert(l<=r);
    int k=__lg(r-l+1);
    return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}
struct edge{
    int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
    e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
    e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int dep[maxn],mxdep[maxn],son[maxn];
ll buf1[maxn<<1],*p1;
int buf2[maxn<<2],*p2;
ll *f[maxn];
int *L[maxn],*R[maxn];
void dfs1(int u,int fa,int d){
    dep[u]=d,mxdep[u]=d;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u,d+1);
        if(mxdep[v]>mxdep[u]) son[u]=v,mxdep[u]=mxdep[v];
    }
}
void dfs2(int u,int fa){
    if(u==1){
        f[u]=p1,p1+=mxdep[u]-dep[u]+1;
        L[u]=p2,p2+=mxdep[u]-dep[u]+1;
        R[u]=p2,p2+=mxdep[u]-dep[u]+1;
        for(int d=0;d<=mxdep[u]-dep[u];++d) f[u][d]=0,L[u][d]=-1,R[u][d]=-1;
    }
    if(!son[u]) return;
    f[son[u]]=f[u]+1,L[son[u]]=L[u]+1,R[son[u]]=R[u]+1;
    dfs2(son[u],u);
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa||v==son[u]) continue;
        f[v]=p1,p1+=mxdep[v]-dep[v]+1;
        L[v]=p2,p2+=mxdep[v]-dep[v]+1;
        R[v]=p2,p2+=mxdep[v]-dep[v]+1;
        for(int d=0;d<=mxdep[v]-dep[v];++d) f[v][d]=0,L[v][d]=-1,R[v][d]=-1;
        dfs2(v,u);
    }
}
void dfs3(int u,int fa){
    f[u][0]=a[0];
    if(!son[u]){
        L[u][0]=R[u][0]=dep[u];
        // cerr<<"u:"<<u<<endl;
        // for(int d=0;d<=mxdep[u]-dep[u];++d){
        //     cerr<<"d:"<<d<<" f:"<<f[u][d]<<" L:"<<L[u][d]<<" R:"<<R[u][d]<<endl;
        // }
        return;
    }
    dfs3(son[u],u);
    int mx=0;
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa||v==son[u]) continue;
        dfs3(v,u);
        mx=max(mx,mxdep[v]-dep[v]);
    }
    for(int d=0;d<=mx;++d){
        if(L[son[u]][d]!=-1&&d+1<=mxdep[son[u]]-dep[son[u]]){
            if(L[son[u]][d+1]==-1) L[son[u]][d+1]=L[son[u]][d],R[son[u]][d+1]=R[son[u]][d];
            else L[son[u]][d+1]=L[son[u]][d];
        }
        // cerr<<"u:"<<u<<" son:"<<son[u]<<" ["<<dep[son[u]]+d-R[son[u]][d]<<","<<dep[son[u]]+d-L[son[u]][d]<<"]"<<endl;
        if(L[son[u]][d]!=-1) f[son[u]][d]=min(f[son[u]][d],(ll)query(dep[son[u]]+d-R[son[u]][d],dep[son[u]]+d-L[son[u]][d]));
        L[son[u]][d]=R[son[u]][d]=-1;
    }
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==fa||v==son[u]) continue;
        for(int d=0;d<=mxdep[v]-dep[v];++d){
            if(L[v][d]!=-1&&d+1<=mxdep[v]-dep[v]){
                if(L[v][d+1]==-1) L[v][d+1]=L[v][d],R[v][d+1]=R[v][d];
                else L[v][d+1]=L[v][d];
            }
            // cerr<<"u:"<<u<<" v:"<<son[u]<<" ["<<dep[v]+d-R[v][d]<<","<<dep[v]+d-L[v][d]<<"]"<<endl;
            if(L[v][d]!=-1) f[v][d]=min(f[v][d],(ll)query(dep[v]+d-R[v][d],dep[v]+d-L[v][d]));
            L[v][d]=R[v][d]=-1;
            f[u][d+1]+=f[v][d];
        }
    }
    L[u][0]=R[u][0]=dep[u];
    // cerr<<"u:"<<u<<endl;
    // for(int d=0;d<=mxdep[u]-dep[u];++d){
    //     cerr<<"d:"<<d<<" f:"<<f[u][d]<<" L:"<<L[u][d]<<" R:"<<R[u][d]<<endl;
    // }
}
ll ans;

int main(){
    // freopen("e.in","r",stdin);
    t=read();
    while(t--){
        n=read();
        for(int i=0;i<n;++i) a[i]=read();
        build();
        cnt=0;
        for(int i=1;i<=n;++i) head[i]=0;
        for(int i=1,u,v;i<n;++i){
            u=read(),v=read();
            add_edge(u,v);
            if(n==54) cout<<u<<" "<<v<<endl;
        }
        p1=buf1,p2=buf2;
        dfs1(1,0,0);
        // for(int u=1;u<=n;++u) cerr<<"u:"<<u<<" son:"<<son[u]<<endl;
        dfs2(1,0);
        dfs3(1,0);
        ans=0;
        for(int d=0;d<=mxdep[1];++d){
            if(L[1][d]!=-1&&d+1<=mxdep[1]){
                if(L[1][d+1]==-1) L[1][d+1]=L[1][d],R[1][d+1]=R[1][d];
                else L[1][d+1]=L[1][d];
            }
            if(L[1][d]!=-1) f[1][d]=min(f[1][d],(ll)query(dep[1]+d-R[1][d],dep[1]+d-L[1][d]));
            ans+=f[1][d];
        }
        printf("%lld\n",ans);
    }
    return 0;
}