#include <bits/stdc++.h>
#define ll long long
#define int long long
#define eps 1e-12
#define db long double
#define ull unsigned long long
#define wr(x,ch) write(x),putchar(ch)
#define lb(x) ((x)&-(x))
using namespace std;
typedef pair<ll,ll> pai;
#define x first
#define y second
ll read() {
	ll x=0;
	bool f=0;char c=getchar();
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
void write(ll x) {
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=155;
int dp[N][N][N],siz[N],dep[N],n,u,v,ans,a[N],s[N],fa[N],sta[N],top;
vector<int> G[N];
void dfs(int p) {
	siz[p]=1;
	for(const auto &lxl:G[p]) 
		if(lxl!=fa[p]) 
			fa[lxl]=p,dfs(lxl),siz[p]+=siz[lxl];
	return ;
}
int calc(int x,int y) {
	if(fa[x]==y) return siz[x];
	else return n-siz[y];
}
bool getr(int p,int fa,int t) {
	sta[++top]=p;
	s[top]=calc(sta[top],sta[top-1]);
	if(t==p) return 1;
	for(const auto &lxl:G[p]) 
		if(lxl!=fa) {
			if(getr(lxl,p,t)) return 1;
		}
	top--;
	return 0;
}
void solve() {
	for(int i=1;i<top;i++) s[i]-=s[i+1]-1;
	for(int i=2;i<=top;i++) s[i]+=s[i-1];
	for(int i=1;i<=top;i++) 
		for(int j=i;j<=top;j++) 
			for(int k=0;k<n;k++) dp[i][j][k]=0;
	for(int len=2;len<=top;len++) {
		for(int l=1,r=len;r<=top;l++,r++) {
			for(int t=1;t<n;t++) {
				dp[l][r][t]=dp[l][r][t-1];
				if(t<=s[r-1]-s[l-1]+(r-l)+1) dp[l][r][t]=max(dp[l][r][t],dp[l][r-1][t-1]+a[t]);
				if(t<=s[r]-s[l]+(r-l)+1) dp[l][r][t]=max(dp[l][r][t],dp[l+1][r][t-1]+a[t]);
			}
		}
	}
	ans=max(ans,dp[1][top][n-1]);
	return ;
}
void Solve(int op) {
	n=1+read();
	for(int i=1;i<=n;i++) G[i].clear();
	for(int i=1;i<n;i++) a[i]=read();
	for(int i=1;i<n;i++) u=read(),v=read(),G[u].push_back(v),G[v].push_back(u);
	dfs(1);
	ans=0;
	if(op) {printf("%c",(n>20)^48);
	return ;
	}
	for(int i=1;i<=n;i++) {
		for(int j=i+1;j<=n;j++) {
			if(G[i].size()==1&&G[j].size()==1) {
				top=0;
				getr(i,0,j);
				solve();
			}
		}
	}
	wr(ans,'\n');
	return ;
}
signed main() {
	int t=read();
	while(t--) Solve(t>1000);
	return 0;
}