#include<bits/stdc++.h>
using namespace std;
const int N=152;
long long F[N][N][N];
int n,s[N];
vector<vector<int>>S;
vector<int>to[N];
int sta[N],MD,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&&to[u].size()==1)
    {
        if(MD<top)MD=top,S.clear();sta[top]=0;
        if(MD==top)S.push_back(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;}
__inline void ckmax(long long&A,long long B){(A<B)?(A=B):0;}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T,U=0,C=0;
    cin>>T;U=T>10;
    while(T--)
    {
        ++C;
        cin>>n;++n;MD=0;
        long long 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)ini(i,0),dfs(i,0,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<MD;++l)
                    for(int r=0;r<MD;++r)
                        F[i][l][r]=0;
            for(int i=0;i<MD;++i)s[i]=(i?s[i-1]:0)+A[i];
            for(int i=0;i<MD;++i)F[0][i][i]=0;
            for(int i=0;i<n-1;++i)
                for(int l=0;l<MD;++l)
                    for(int r=l;r<MD;++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]);
                            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<MD;++l)
            //         for(int r=l;r<MD;++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][MD-1]);
        }
        S.clear();
        if(!U)cout<<ans<<endl;
        else if(C==48)
        {
            for(int i=1;i<=n;++i)
                for(int j:to[i])cout<<i<<" "<<j<<endl;
            for(int i=0;i<n-1;++i)cout<<a[i]<<"_";cout<<endl;
        }
        for(int i=1;i<=n;++i)to[i].clear();
    }
}