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

void solve(){
    int n;
    cin>>n;
    vector<long long>a(n);
    for(auto &i:a) cin>>i;
    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);
    vector f(n+1,vector(n+1,0ll));
    auto dfs=[&](auto dfs,int u,int fa)->void{
        dep[u]=dep[fa]+1;
        for(auto v:e[u]){
            if(v==fa) continue;
            dfs(dfs,v,u);
        }
        f[u][0]=a[0];
        vector g(n+1,0ll);
        for(int i=1;i<=n;++i){
            for(auto v:e[u]){
                if(v==fa) continue;
                g[i]+=f[v][i-1];
            }
            f[u][i]=min(a[i],g[i]);
        }
    };
    dfs(dfs,1,0);
    long long res=0;
    for(int i=0;i<n;++i) res+=f[1][i];
    cout<<res<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
}