#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=153;
int n,a[N];
ll f[N][N][N];
vector<int>G[N];
int rt;
int sz[N][N],F[N][N];
inline void dfs(int u,int fa){
	F[rt][u]=fa; sz[rt][u]=1;
	for(int v:G[u])if(v!=fa)dfs(v,u),sz[rt][u]+=sz[rt][v];
}
inline void ck(ll &x,ll y){if(y>x)x=y;}
inline void solve(){
	n=read();rep(i,1,n)a[i]=read();
	rep(i,1,n+1)G[i].clear();
	rep(i,1,n){
		int u=read(),v=read();
		G[u].pb(v),G[v].pb(u);
	}
	rep(i,1,n+1) dfs(rt=i,0);
	rep(i,0,n)rep(j,1,n+1)rep(k,1,n+1)f[i][j][k]=0;
	rep(i,1,n+1)f[0][i][i]=0;
	rep(i,0,n-1)rep(u,1,n+1)rep(v,1,n+1)if(f[i][u][v]!=-1){
		ck(f[i+1][u][v],f[i][u][v]);
		for(int w:G[u])if(w!=F[v][u]&&i<=n-sz[v][w])ck(f[i+1][w][v],f[i][u][v]+a[i+1]);
		if(u==v)continue;
		for(int w:G[v])if(w!=F[u][v]&&i<=n-sz[u][w])ck(f[i+1][u][w],f[i][u][v]+a[i+1]);
	}
	ll ans=0;
	rep(u,1,n+1)rep(v,1,n+1)ans=max(ans,f[n][u][v]);
	printf("%lld\n",ans);
}
int main() {
    //freopen("data.in", "r", stdin);
    // freopen("myans.out","w",stdout);
	int T=read();while(T--)solve();
    return 0;
}