#include<bits/stdc++.h>
using namespace std;
const int maxn=150+5,M=3e5+5;
#define pb push_back
inline int read(){
    char ch=getchar();int x=0;bool f=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1){x=-x;}return x;
}
int T,n,m,x,y,a[maxn];
long long f[maxn][maxn],g[maxn][maxn];
int sz[maxn],mx,F,flag[maxn];
int s[maxn],dis[maxn];
int D[maxn],cnt=0;
vector<int>e[maxn];
void dfs(int x,int fa){
    dis[x]=dis[fa]+1;
    if(dis[mx]<dis[x])mx=x;
    for(auto i:e[x])if(i^fa){
        dfs(i,x);
    }
}
void getd(int x,int fa){
    if(x==mx){
        F=1;D[++cnt]=x;flag[x]=1;
        return;
    }
    for(auto i:e[x])if(i!=fa&&!F){
        getd(i,x);
    }
    if(F)D[++cnt]=x,flag[x]=1;
}
void getsz(int x,int fa){
    sz[x]++;
    for(auto i:e[x])if(i!=fa&&!flag[i]){
        getsz(i,x);sz[x]+=sz[i];
    }
}
int o=0;
void solve(){
    n=read();
    o++; if(o==48)cout<<n<<endl;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(o==48)cout<<a[i]<<" ";
    }
   
    
    n++;
    for(int i=1;i<n;i++){
        x=read(),y=read(),e[x].pb(y),e[y].pb(x);
        if(o==48)cout<<x<<" "<<y<<endl;
    }//return ;
    dfs(1,0);dis[mx]=0;int z=mx;
    dfs(z,0);F=0;cnt=0;
    getd(z,0);//return;
    for(int i=0;i<=cnt;i++)getsz(D[i],0);
    for(int j=1;j<=cnt;j++)s[j]=s[j-1]+sz[D[j]]-1;
    for(int i=1;i<=cnt;i++)
        for(int j=i;j<=cnt;j++)f[i][j]=0;
    for(int i=1;i<n;i++){
        for(int j=1;j<=cnt;j++){
            for(int k=j;k<=cnt;k++){
                g[j][k]=0;
                if(s[k]-s[j-1]>=i-(k-j))g[j][k]=max(f[j][k],g[j][k]);
                if(j!=k)g[j][k]=max(g[j][k],f[j+1][k]+a[i]);
                if(j!=k)g[j][k]=max(g[j][k],f[j][k-1]+a[i]);
                //cout<<g[j][k]<<" "<<j<<" "<<k<<endl;
            }
        }
        for(int j=1;j<=cnt;j++)
            for(int k=j;k<=cnt;k++)
                f[j][k]=g[j][k];
    }
    if(T<=3)cout<<f[1][cnt]<<endl;
    mx=0;F=0;
    for(int i=1;i<=n;i++)e[i].clear(),dis[i]=0,flag[i]=0;
}
signed main(){
    T=read();
    while(T--){
        solve();
    }
    return 0;
}