#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=3e5+10;
int lg[maxn];

void solve(){
    int n;
    cin>>n;
    vector<ll>a(n);
    vector<vector<ll>>st(n,vector<ll>(20));
    for(int i=0;i<n;i++){
        cin>>a[i];
        st[i][0]=a[i];
    }
    for(int j=1;j<=19;j++){
        for(int i=0;i<n&&i+1<<j<n;i++){
            st[i][j]=min(st[i][j-1],st[i+1<<j][j-1]);
        }
    }
    auto mn=[&](int l,int r)->ll{
    	int x=lg[r-l+1];
    	return min(st[l][x],st[r-(1<<x)+1][x]);
    };
    vector<vector<int>>e(n+1);
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int>dep(n+1),dfn(n+1);
    vector<vector<int>>cur(n+1);
    vector<vector<int>>fax(n+1,vector<int>(20));
    int tot=0;
    dep[0]=-1;
    auto dfs=[&](auto dfs,int u,int fa)->void{
        dfn[u]=++tot;
        dep[u]=dep[fa]+1;
        fax[u][0]=fa;
        for(int i=1;i<=19;i++){
        	fax[u][i]=fax[fax[u][i-1]][i-1];
        }
        cur[dep[u]].push_back(u);
        for(auto v:e[u]){
            if(v==fa) continue;
            dfs(dfs,v,u);
        }
    };
    auto lca=[&](int x,int y)->int{
		if(dep[x]<dep[y]){
			swap(x,y);
		}
		for(int i=19;i>=0;i--){
			if(dep[fax[x][i]]>=dep[y]){
				x=fax[x][i];
			}
		}
		if(x==y)return x;
		for(int i=19;i>=0;i--){
			if(fax[x][i]!=fax[y][i]){
				x=fax[x][i],y=fax[y][i];
			}
		}
		return fax[x][0];
	};
    auto solve=[&](int depp)->int{
        if(!cur[depp].size()){
            return 0;
        }

        cur[depp].push_back(1);
        sort(cur[depp].begin(),cur[depp].end(),[&](int x,int y){
            return dfn[x]<dfn[y];
        });

        vector<int>now=cur[depp];
        for(int i=1;i<cur[depp].size();i++){
        	
            int lc=lca(cur[depp][i],cur[depp][i-1]);
            //cerr<<cur[depp][i]<<' '<<cur[depp][i-1]<<' '<<depp<<' '<<lc<<'\n';
            now.push_back(lc);
        }
        sort(now.begin(),now.end(),[&](int x,int y){
            return dfn[x]<dfn[y];
        });
        now.erase(unique(now.begin(),now.end()),now.end());
        int sz=now.size();
        vector<vector<int>>g(sz);
        vector<ll>dp(sz,0);
        // for(int i=0;i<sz;i++){
        // 	cerr<<now[i]<<' ';
        // }
        // cerr<<depp<<'\n';
        for(int i=1;i<sz;i++){
            int lc=lca(now[i-1],now[i]);
            int pos=lower_bound(now.begin(),now.end(),lc)-now.begin();
            g[pos].push_back(i);
        }
        auto dfss=[&](auto dfss,int u,int fa)->void{

            dp[u]=a[depp-dep[now[u]]];
            ll res=0;
            for(auto v:g[u]){
            	if(v==fa){
            		continue;
            	}
            	dfss(dfss,v,u);
            	res+=min(mn(depp-dep[now[v]],depp-dep[now[u]]-1),dp[v]);
            }

            if(res){
            	dp[u]=min(dp[u],res);
            } 
        };

        dfss(dfss,0,-1);
        return dp[0];
    };
    dfs(dfs,1,0);
    ll ans=0;
    for(int i=0;i<n;++i) ans+=solve(i);
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=300000;i++){
        lg[i]=lg[i-1]+(i==(1<<(lg[i-1]+1)));
    }
    int T;cin>>T;
    while(T--) solve();
}