#include<bits/stdc++.h>
using namespace std;
const int N=152;
long long F[N][N][N];
int n,s[N];
set<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)sta[top]=0,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;}
__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;cin>>T;
    while(T--)
    {
        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);
        for(const vector<int>&A:S)
        {
            MD=A.size();
            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<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)>=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<MD)ckmax(F[i+1][l][r+1],F[i][l][r]+a[i]);
                        }
            ckmax(ans,F[n-1][0][MD-1]);
        }
        S.clear();
        cout<<ans<<endl;
        for(int i=1;i<=n;++i)to[i].clear();
    }
}