// Hydro submission #678f50e53e10c2b5101fa6a8@1737445606367
#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<<2];
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));
    for(auto y:g[x]) dfs1(y,x,D);
    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();
    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;
}

answer.code:8:7: error: expected nested-name-specifier before ‘ll’
    8 | using ll=long long;
      |       ^~
answer.code:9:7: error: expected nested-name-specifier before ‘PII’
    9 | using PII=pair<int,int>;
      |       ^~~
answer.code: In function ‘void dfs(int, int)’:
answer.code:22:14: error: ‘y’ does not name a type
   22 |     for(auto y:eg[x]) if(y!=from) dfs(y,x);
      |              ^
answer.code:22:44: error: expected ‘;’ before ‘}’ token
   22 |     for(auto y:eg[x]) if(y!=from) dfs(y,x);
      |                                            ^
      |                                            ;
   23 | }
      | ~                                           
answer.code:23:1: error: expected primary-expression before ‘}’ token
   23 | }
      | ^
answer.code:22:44: error: expected ‘;’ before ‘}’ token
   22 |     for(auto y:eg[x]) if(y!=from) dfs(y,x);
      |                                            ^
      |                                            ;
   23 | }
      | ~                                           
answer.code:23:1: error: expected primary-expression before ‘}’ token
   23 | }
      | ^
answer.code:22:44: error: expected ‘)’ before ‘}’ token
   22 |     for(auto y:eg[x]) if(y!=from) dfs(y,x);
      |        ~                                   ^
      |                                            )
   23 | }
      | ~                                           
answer.code:23:1: error: expected primary-expression before ‘}’ token
   23 | }
      | ^
answer.code: At global scope:
answer.code:34:1: error: ‘ll’ does not name a type
   34 | ll f[N];
      | ^~
answer.code: In function ‘void dfs1(int, int, int)’:
answer.code:38:5: error: ‘f’ was not declared in this scope
   38 |     f[x]=GetMin(D-dep[x],D-(dep[from]+1));
      |     ^
answer.code:39:14: error: ‘y’ does not name a type
   39 |     for(auto y:g[x]) dfs1(y,x,D);
      |              ^
answer.code:39:34: error: expected ‘;’ before ‘if’
   39 |     for(auto y:g[x]) dfs1(y,x,D);
      |                                  ^
      |                                  ;
   40 |     if(g[x].size())  {
      |     ~~                            
answer.code:40:5: error: expected primary-expression before ‘if’
   40 |     if(g[x].size())  {
      |     ^~
answer.code:39:34: error: expected ‘;’ before ‘if’
   39 |     for(auto y:g[x]) dfs1(y,x,D);
      |                                  ^
      |                                  ;
   40 |     if(g[x].size())  {
      |     ~~                            
answer.code:40:5: error: expected primary-expression before ‘if’
   40 |     if(g[x].size())  {
      |     ^~
answer.code:39:34: error: expected ‘)’ before ‘if’
   39 |     for(auto y:g[x]) dfs1(y,x,D);
      |        ~                         ^
      |                                  )
   40 |     if(g[x].size())  {
      |     ~~                            
answer.code:41:9: error: ‘ll’ was not declared in this scope
   41 |         ll res=0;
      |         ^~
answer.code:42:18: error: ‘y’ does not name a type
   42 |         for(auto y:g[x]) res+=f[y];
      |                  ^
answer.code:42:36: error: expected ‘;’ before ‘f’
   42 |         for(auto y:g[x]) res+=f[y];
      |                                    ^
      |                                    ;
   43 |         f[x]=min(f[x],res);
      |         ~                           
answer.code:43:23: error: ‘res’ was not declared in this scope
   43 |         f[x]=min(f[x],res);
      |                       ^~~
answer.code:44:5: error: expected primary-expression before ‘}’ token
   44 |     }
      |     ^
answer.code:43:28: error: expected ‘)’ before ‘}’ token
   43 |         f[x]=min(f[x],res);
      |                            ^
      |                            )
   44 |     }
      |     ~                       
answer.code:42:12: note: to match this ‘(’
   42 |         for(auto y:g[x]) res+=f[y];
      |            ^
answer.code:44:5: error: expected primary-expression before ‘}’ token
   44 |     }
      |     ^
answer.code: At global scope:
answer.code:46:1: error: ‘ll’ does not name a type
   46 | ll ans;
      | ^~
answer.code: In function ‘void sol(std::vector<int>&, int)’:
answer.code:48:83: warning: lambda expressions only available with ‘-std=c++11’ or ‘-std=gnu++11’ [-Wc++11-extensions]
   48 |     sort(nd.begin(),nd.end(),[](const int &x,const int &y){ return dfn[x]<dfn[y]; });
      |                                                                                   ^
answer.code:48:9: error: no matching function for call to ‘sort(std::vector<int>::iterator, std::vector<int>::iterator, sol(std::vector<int>&, int)::<lambda(const int&, const int&)>)’
   48 |     sort(nd.begin(),nd.end(),[](const int &x,const int &y){ return dfn[x]<dfn[y]; });
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits...