#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define int long long
using namespace std;
const int N=160;
int n,a[N],dp[N][N][N],u,v,inch[N],ans,sz[N];
vector<int> adj[N],stk;
void calcsz(int u,int p,int grp){
    sz[grp]++;
    for (int i:adj[u]) if (!inch[i]&&i!=p) calcsz(i,u,grp);
}
void dfs(int u,int dep){
    stk.push_back(u);
    inch[u]=dep;
    if (adj[u].size()==1&&dep>1&&stk[0]<stk.back()){
        //for (int i:stk) cout<<i<<"-";
        //cout<<"::\n";
        for (int i=0;i<dep;i++){
            sz[i]=-1;
            calcsz(stk[i],stk[i],i);
            //cout<<stk[i]<<": "<<sz[i]<<"\n";
        }
        for (int i=0;i<=dep;i++) for (int j=0;j<=dep;j++) for (int k=0;k<=n;k++) dp[i][j][k]=-1e15;
        for (int i=0;i<dep;i++) for (int k=0;k<=sz[i];k++) dp[i][i][k]=0;
        for (int i=1;i<dep;i++) sz[i]+=sz[i-1];
        for (int len=1;len<dep;len++) for (int j=0;j+len<dep;j++) for (int k=1;k<n;k++) {
            dp[j][j+len][k]=max(dp[j+1][j+len][k-1],dp[j][j+len-1][k-1])+a[k];
            int v=sz[j+len]-(j?sz[j-1]:0)+len;
            /*if (stk[0]==2&&stk.back()==6){
                cout<<j<<" - "<<j+len<<" w "<<k<<": "<<v<<", "<<dp[j][j+len][k]<<"\n";
            }*/
            if (k<=v) dp[j][j+len][k]=max(dp[j][j+len][k],dp[j][j+len][k-1]);
        }
        ans=max(ans,dp[0][dep-1][n-1]);
        //cout<<dp[0][dep-1][n-1]<<"!\n";
    }
    for (int i:adj[u]) if (!inch[i]) dfs(i,dep+1);
    stk.pop_back();
    inch[u]=0;
}
void solve() {
    cin>>n;
    n++;
    for (int i=1;i<n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) adj[i].clear();
    for (int i=1;i<n;i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    ans=-1e15;
    for (int i=1;i<=n;i++) if (adj[i].size()==1) dfs(i,1);
    cout<<ans<<"\n";
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(false);

    int t = 1; cin >> t;
    while (t--) {
        solve();
    }
}