#include<bits/stdc++.h>
using namespace std;
const int N=152;
int F[N][N][N],n,s[N];
set<vector<int>>S;
vector<int>to[N];
int sta[N],mxdep,sz[N];
void ini(int u,int f){sz[u]=1;for(int v:to[u])if(v!=f)ini(v,u),sz[u]+=sz[v];}
void dfs(int u,int f,int top)
{
    if(f!=u&&f&&to[u].size()==1)
    {
        if(mxdep<top)mxdep=top,S.clear();sta[top]=0;
        if(mxdep==top)S.insert(vector<int>(sta+1,sta+top+1));
    }
    for(int v:to[u])if(v!=f)
    {
        sta[top]=sz[u]-sz[v]-1;
        dfs(v,u,top+1);
    }
}
int a[N];
__inline void ckmax(int&A,int B){(A<B)?(A=B):0;}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;++n;mxdep=0;
        int ans=0;
        for(int i=0;i<n-1;++i)cin>>a[i];
        for(int i=1,u,v;i<n;++i)cin>>u>>v,to[u].push_back(v),to[v].push_back(u);
        for(int i=1;i<=n;++i)if(to[i].size()==1)/*cerr<<"DFS: "<<i<<endl,*/ini(i,0),dfs(i,i,1);
        // cerr<<"ED\n";
        for(const vector<int>&A:S)
        {
            // cerr<<A.size()<<": ";
            // for(auto k:A)cerr<<k<<"_";cerr<<endl;
            for(int i=0;i<n;++i)
                for(int l=0;l<mxdep;++l)
                    for(int r=0;r<mxdep;++r)
                        F[i][l][r]=-1e9;
            for(int i=0;i<mxdep;++i)s[i]=(i?s[i-1]:0)+A[i];
            for(int i=0;i<mxdep;++i)F[0][i][i]=0;
            for(int i=0;i<n-1;++i)
                for(int l=0;l<mxdep;++l)
                    for(int r=l;r<mxdep;++r)
                        if(s[r]-(l?s[l-1]:0)+(r-l+1)>=i)
                        {
                            ckmax(F[i+1][l][r],F[i][l][r]);
                            if(l)ckmax(F[i+1][l-1][r],F[i][l][r]+a[i]);
                            if(r+1!=mxdep)ckmax(F[i+1][l][r+1],F[i][l][r]+a[i]);
                        }
            // for(int i=0;i<=n;++i)
            //     for(int l=0;l<mxdep;++l)
            //         for(int r=l;r<mxdep;++r)
            //             if(s[r]-(l?s[l-1]:0)+(r-l+1)>=i)
            //                 cerr<<"F "<<i<<" "<<l<<"~"<<r<<" : "<<F[i][l][r]<<endl;
            ckmax(ans,F[n-1][0][mxdep-1]);
        }
        S.clear();
        for(int i=1;i<=n;++i)to[i].clear();
        cout<<ans<<endl;
    }
}