#include<bits/stdc++.h>
#define int long long

using namespace std;
const int inf=1e18;

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