#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+50;

struct edge
{
    int u,v,nxt;
}e[N];

int a[N][20],n,dep[N],head[N],T,lg[N],cnt,fa[N],top[N],siz[N],son[N],f[N];
ll ans;
vector<int>in[N];

void clear()
{
    ans=cnt=0;
    for(int i=1;i<=n;i++)
    {
        vector<int>().swap(in[i]);
        son[i]=f[i]=siz[i]=top[i]=fa[i]=head[i]=dep[i]=0;
    }
}

int find(int l,int r)
{
    int k=lg[r-l+1]-1;
    return min(a[l][k],a[r-(1<<k)+1][k]);
}

void dfs1(int x,int f)
{
    fa[x]=f;siz[x]=1;dep[x]=dep[f]+1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs1(v,x);siz[x]+=siz[v];
        if(siz[v]>siz[son[x]])son[x]=v;
    }
}

void dfs2(int x,int topp)
{
    top[x]=topp;in[dep[x]].push_back(x);
    if(!son[x])return;dfs2(son[x],topp);
    for(int i=head[x];i;i=e[i].nxt)if(e[i].v!=fa[x]&&e[i].v!=son[x])dfs2(e[i].v,e[i].v);
}

int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

vector<int>to[N];

void solve(int x,int fa,int d)
{
    if(dep[x]==d)
    {
        f[x]=find(0,d-1);
        return;
    }
    ll w=0;
    for(auto v:to[x])solve(v,x,d),w+=f[v];
    f[x]=min(w,1ll*find(d-dep[x],d-1));
}

void clear(int x)
{
    for(auto v:to[x])clear(v);
    vector<int>().swap(to[x]);
}

void solve(vector<int>&a)
{
    int now=a[0],d=dep[now];a.push_back(1);
    for(auto x:a)if(x!=now)
    {
        int lca=LCA(now,x);
        if(x!=lca)to[lca].push_back(x);
        if(now!=lca)to[lca].push_back(now);
        now=lca;
    }
    solve(1,0,d);
    ans+=f[1];clear(1);
}

void sol()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i][0];
    for(int j=1;(1<<j)<=n;j++)for(int i=0;i+(1<<j)<=n;i++)a[i][j]=min(a[i][j-1],a[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e[++cnt]=(edge){u,v,head[u]};head[u]=cnt;
        e[++cnt]=(edge){v,u,head[v]};head[v]=cnt;
    }
    dfs1(1,1);dfs2(1,1);
    for(int i=1;i<=n;i++)if(in[i].size())solve(in[i]);
    cout<<ans<<'\n';
}

main()
{
    // freopen("in.txt","r",stdin);
    cin>>T;
    while(T--)sol(),clear();
}