#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
    int res=0; bool f=0;
    char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) res=res*10+(ch^'0'),ch=getchar();
    return f?-res:res;
}
const int N=200010,M=N<<1,inf=1e9;
int n,a[N],s[N];
int idx=1,e[M],ne[M],head[N];
inline void add(int x,int y) {
    e[++idx]=y;
    ne[idx]=head[x];
    head[x]=idx;
}
ll space[N],*tmp,*f[N];
int son[N],depth[N];
int d[N]; // 到根距离
void dfs(int u,int fa) {
    son[u]=0;
    for(int i=head[u];i;i=ne[i]) {
        int v=e[i];
        if(v==fa) continue;
        d[v]=d[u]+1;
        dfs(v,u);
        if(depth[v]>depth[son[u]]) son[u]=v;
    }
    depth[u]=depth[son[u]]+1;
}
void dp(int u,int fa) {
    f[u]=++tmp; f[u][0]=s[d[u]];
    if(son[u]) dp(son[u],u);
    for(int i=head[u];i;i=ne[i]) {
        int v=e[i];
        if(v==fa||v==son[u]) continue;
        dp(v,u);
        for(int i=0;i<depth[v];i++) {
            f[u][i+1]+=f[v][i];
            f[u][i+1]=min(f[u][i+1],1ll*a[i+1]);
        }
    }
}
int main() {
    int TT=read();
    while(TT--) {
        n=read();

        idx=1; for(int i=1;i<=n;i++) head[i]=0; 

        for(int i=0;i<n;i++) a[i]=read(),s[i]=min((i?s[i-1]:inf),a[i]);
        for(int i=1;i<n;i++) {
            int a=read(),b=read();
            add(a,b); add(b,a);
        }
        dfs(1,0); 
        tmp=space;
        dp(1,0);
        ll ans=0;
        for(int i=0;i<depth[1];i++) ans+=f[1][i];
        printf("%lld\n",ans);
        while(tmp!=space) (*tmp)=0,tmp--; // 清空
        (*tmp)=0; // space 也要清
    }
    return 0;
}