#include<bits/stdc++.h>
using namespace std;
const int S=200005;
int e,siz[S],dep[S],fa[S],DEEP[S],link[S],head[S],to[S],son[S],n;
void dfs(int u,int FA) {
    siz[u]=1,fa[u]=FA,dep[u]=dep[FA]+1,DEEP[u]=dep[u];
    for(int i=head[u];i;i=link[i]) {
        int v=to[i];
        if(v==FA)continue;
        dfs(v,u);
        siz[u]+=siz[v];
        DEEP[u]=max(DEEP[u],DEEP[v]);
        if(DEEP[son[u]]<DEEP[v])son[u]=v;
    }
}
int a[S],link_id[S];
vector<pair<long long, pair<int, int> > > ve[S];
int ST[S][25],i2[S];
int Qry(int l,int r) {
    return min(ST[l][i2[r-l+1]], ST[r-(1<<i2[r-l+1])+1][i2[r-l+1]]);
}
const int INF = 1e9;
void Clr(int x, int cur) {
    int L = INF, R = -INF, siz = ve[x].size();
    for (int i = siz - 1; i >= siz - cur; i--) {
        if (L != INF) {
            L++, R++;
        }
        if (ve[x][i].second.first != -1) {
            L = min(L, ve[x][i].second.first);
            R = max(R, ve[x][i].second.second);
            ve[x][i].second = make_pair(-1, -1);
        }
        if (L == INF) continue;
        ve[x][i].first = min(ve[x][i].first, Qry(L, R)*1ll);
    }
    if (L != INF && siz - cur - 1 > 0) {
        if (ve[x][siz - cur - 1].second.first == -1)
            ve[x][siz - cur - 1].second = make_pair(L, R);
        else {
            ve[x][siz - cur - 1].second.first = min(ve[x][siz - cur - 1].second.first, L);
            ve[x][siz - cur - 1].second.second = max(ve[x][siz - cur - 1].second.second, R);
        }
    }
}
int dfs1(int u) {
    if (son[u]) {
        link_id[u] = dfs1(son[u]);
    } else {
        link_id[u] = u;
    }
    int x = link_id[u];
    int cur=-INF;
    ve[x].push_back(make_pair(a[0], make_pair(-1, -1)));
    for (int i=head[u];i;i=link[i])
        if (to[i]!=son[u] && to[i]!=fa[u]) {
            cur=max(cur,DEEP[to[i]]);
        }
    if (cut > -INF) {
        cur = cur - dep[u] + 1;
        //cur++;
        Clr(x, cur);
    }
    int szx = ve[x].size();
    for (int i=head[u];i;i=link[i])
        if (to[i]!=son[u] && to[i]!=fa[u]) {
            int o = dfs1(to[i]);
            Clr(o, ve[o].size());
            for (int sz=ve[o].size(),j=sz-1;j>=0;--j) {
                ve[x][szx-(sz-j)-1].first += ve[o][j].first;
                //ve[x][DEEP[u]-DEEP[to[i]]+j].first += ve[o][j].first;
            }
            ve[o].clear();
        }
    ve[x][szx - 1].second = make_pair(0, 0);
    //ve[x][DEEP[u]].second = make_pair(0, 0);
    return x;
}
void add(int uu,int vv) {
    to[++e]=vv;
    link[e]=head[uu];
    head[uu]=e;
}
int main() {
    int T = 0;
    scanf("%d",&T);
    i2[1]=0;
    for (int i=2;i<S;++i)
        i2[i]=i2[i>>1]+1;
    while(T--) {
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d",&a[i]),ST[i][0]=a[i];
        e=0;
        for(int i=1;i<=n;i++)
            head[i]=0,ve[i].clear(), son[i] = 0, link_id[i] = 0;
        for (int i=1;(1<<i)<=n;++i)
            for (int j=0;j+(1<<i)-1<n;++j)
                ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
        for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
        //printf("NMSL---------\n");
        DEEP[0] = 0, dep[0] = -1, dfs(1,0);
        //printf("NMSL---------\n");
        int x = dfs1(1);
        //printf("NMSL---------\n");
        Clr(x, ve[x].size());
        long long ans = 0;
        for (int i = 0, siz = ve[x].size(); i < siz; i++)
            ans += ve[x][i].first;
        printf("%lld\n", ans);
    }
    return 0;
}

answer.code: In function ‘int dfs1(int)’:
answer.code:59:9: error: ‘cut’ was not declared in this scope; did you mean ‘cur’?
   59 |     if (cut > -INF) {
      |         ^~~
      |         cur
answer.code: In function ‘int main()’:
answer.code:86:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
answer.code:91:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   91 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
answer.code:92:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |         for(int i=0;i<n;i++)scanf("%d",&a[i]),ST[i][0]=a[i];
      |                             ~~~~~^~~~~~~~~~~~
answer.code:99:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   99 |         for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
      |                                 ~~~~~^~~~~~~~~~~~~~