#include<bits/stdc++.h>
#define Lson (now<<1)
#define Rson (now<<1|1)
using namespace std;

typedef long long ll;

const int MAXN=1e5,SIZE=262144,INF=1e9;

int T,n;ll A[MAXN],ans;
vector<int> Tree[MAXN+5],buc[MAXN+5];
int fa[MAXN+5],depth[MAXN+5],DFN[MAXN+5],Head[MAXN+5],Size[MAXN+5],tot;
int stk[MAXN+5],tp;
vector<int> VT[MAXN+5];

void CalMsg(int now)
{
    depth[now]=depth[fa[now]]+1;
    Size[now]=1;
    for(auto rear : Tree[now])
    {
        if(rear==fa[now]) continue;
        fa[rear]=now;
        CalMsg(rear);
        Size[now]+=Size[rear];
    }
}
void TCP(int now,int Top)
{
    Head[now]=Top;
    DFN[now]=++tot;
    int Mson=0;
    for(auto rear : Tree[now])
    {
        if(rear==fa[now]) continue;
        if(Size[rear]>Size[Mson]) Mson=rear;
    }
    if(Mson) TCP(Mson,Top);
    for(auto rear : Tree[now])
    {
        if(rear==fa[now] || rear==Mson) continue;
        TCP(rear,rear);
    }
}
inline int LCA(int a,int b)
{
    while(Head[a]!=Head[b])
    {
        if(depth[Head[a]]<depth[Head[b]]) swap(a,b);
        a=fa[Head[a]];
    }
    if(depth[a]<depth[b]) return a;
    return b;
}

ll minn[SIZE+5];
void Build(int now,int L,int R)
{
    if(L==R) {minn[now]=A[L];return;}
    int mid=(L+R)>>1;
    Build(Lson,L,mid);
    Build(Rson,mid+1,R);
    minn[now]=min(minn[Lson],minn[Rson]);
}
ll GetMin(int now,int L,int R,int QL,int QR)
{
    if(QR<L || R<QL) return INF;
    if(QL<=L && R<=QR) return minn[now];
    int mid=(L+R)>>1;
    return min(GetMin(Lson,L,mid,QL,QR),GetMin(Rson,mid+1,R,QL,QR));
}

bool cmp(int a,int b) {return DFN[a]<DFN[b];}
void Clean(int now)
{
    for(auto rear : VT[now]) Clean(rear);
    VT[now].clear();
}

ll dp[MAXN+5];
void Solve(int now,int d)
{
    if(VT[now].empty()) {dp[now]=A[0];return;}
    dp[now]=0;
    for(int rear : VT[now])
    {
        Solve(rear,d);
        dp[now]+=min(dp[rear],GetMin(1,0,n-1,d-depth[rear],d-depth[now]));
    }
    dp[now]=min(dp[now],A[d-depth[now]]);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%lld",&A[i]);
        for(int i=1;i<=n;i++) Tree[i].clear();
        for(int i=1,a,b;i<n;i++)
        {
            scanf("%d %d",&a,&b);
            Tree[a].push_back(b);
            Tree[b].push_back(a);
        }
        CalMsg(1),tot=0,TCP(1,1);
        for(int i=1;i<=n;i++) buc[i].clear();
        for(int i=1;i<=n;i++) buc[depth[i]].push_back(i);
        Build(1,0,n-1);
        ans=0;
        for(int i=1;i<=n;i++)
        {
            if(buc[i].empty()) continue;
            if(i>1) buc[i].push_back(1);
            sort(buc[i].begin(),buc[i].end(),cmp);
            for(auto j : buc[i])
            {
                if(!tp) {stk[++tp]=j;continue;}
                int lca=LCA(stk[tp],j);
                while(tp>1 && depth[lca]<depth[stk[tp-1]]) VT[stk[tp-1]].push_back(stk[tp]),--tp;
                if(depth[lca]<depth[stk[tp]]) VT[lca].push_back(stk[tp--]);
                if(!tp || stk[tp]!=lca) stk[++tp]=lca;
                stk[++tp]=j;
            }
            Solve(1,i);
            ans+=dp[1];
            Clean(1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

  File "answer.code", line 4
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax