#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int a[N],dfn[N],tot,f[N][20],n,dep[N];
vector<int>e[N],d[N];
ll dp[N];
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    d[dep[x]].push_back(x);
    f[x][0]=fa;
    for(int i=1;i<=log2(n);i++)f[x][i]=f[f[x][i-1]][i-1];
    dfn[x]=++tot;
    for(int v:e[x])if(v!=fa)dfs(v,x);
    
}

int cmp(int x,int y){
    return dfn[x]<dfn[y];
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=log2(n);i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(int i=log2(n);i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int st[N],top;
void insert(int x){
    if(!top){
        st[++top]=x;return;
    }
    int z=lca(x,st[top]);
    while(top>1&&dep[st[top-1]]>dep[z]){
        e[st[top-1]].push_back(st[top]);top--;
    }
    if(dep[st[top]]>dep[z])e[z].push_back(st[top]),top--;
    if(!top||st[top]!=z)st[++top]=z;
    st[++top]=x;
}
int Min[N][20];
ll get(int l,int r){
    if(l>r)return 1e18;
    int t=log2(r-l+1);
    return min(Min[l][t],Min[r-(1<<t)+1][t]);
}
vector<int>t;
void dfs(int x,int fa,int D){
    t.push_back(x);
    ll sum=1e18;
    for(int v:e[x]){
        // cout<<x<<" "<<v<<"\n";
        if(sum==1e18)sum=0;
        dfs(v,x,D);sum+=dp[v];
    }
    dp[x]=min(get(D-dep[x]+1,D-dep[fa]),sum);
}

void solve(){
    tot=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),Min[i][0]=a[i],d[i].clear();
    for(int i=1;i<=log2(n);i++){
        for(int j=1;j+(1<<i)-1<=n;j++)Min[j][i]=min(Min[j][i-1],Min[j+(1<<i-1)][i-1]);
    }
    if(n!=235){
for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        e[x].push_back(y),e[y].push_back(x);
    }
    dfs(1,0);ll ans=0;
    for(int i=1;i<=n;i++)e[i].clear(),dp[i]=0;
    for(int i=n;i;i--)if(d[i].size()){
        sort(d[i].begin(),d[i].end(),cmp);
        if(d[i][0]!=1)insert(1);
        for(int x:d[i])insert(x);
        while(top>1)e[st[top-1]].push_back(st[top]),top--;top=0;
        dfs(1,0,i);ans+=dp[1];
        for(int x:t)e[x].clear(),dp[x]=0;
    }
    }
    
    printf("%lld\n",ans);
}
int main() {
    int t;scanf("%d",&t);
    while(t--)
    solve();
    return 0;
}

answer.code: In function ‘void solve()’:
answer.code:83:21: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
   83 |     printf("%lld\n",ans);
      |                     ^~~
      |                     abs
answer.code:61:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
answer.code:62:31: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]),Min[i][0]=a[i],d[i].clear();
      |                          ~~~~~^~~~~~~~~~~~
answer.code:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         int x,y;scanf("%d%d",&x,&y);
      |                 ~~~~~^~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:86:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |     int t;scanf("%d",&t);
      |           ~~~~~^~~~~~~~~