#include<bits/stdc++.h>
#define int long long
using namespace std;
int dep[155],f[155],dp[155][155][155],T,n,h[155];
int u,v,w[155],vis[155],deg[155],cnt,a[155],sum[155];
struct edge{int v,nxt;}e[305];
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;f[u]=fa;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);
	}
}
int lca(int u,int v)
{
	while(u!=v)
	{
		if(dep[u]<dep[v])swap(u,v);
		u=f[u];
	}
	return u;
}
int dfs2(int u,int fa)
{
	int res=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||vis[v])continue;
		res+=dfs2(v,u);
	}
	return res;
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>T;
	while(T--)
	{
		cin>>n;n++;int ans=0;cnt=0;
		for(int i=1;i<n;i++)cin>>w[i];
		for(int i=1;i<=n;i++)h[i]=0,deg[i]=0;
		for(int i=1;i<n;i++)
		{
			cin>>u>>v;deg[u]++;deg[v]++;
			add(u,v);add(v,u);
		}
		dfs(1,0);
		for(int u=1;u<=n;u++)
		{
			if(deg[u]>1)continue;
			for(int v=u+1;v<=n;v++)
			{
				if(deg[v]>1)continue;
				int p=lca(u,v),tot=0;
				for(int i=u;i!=p;i=f[i])a[++tot]=i;
				a[++tot]=p;int pos=tot;
				for(int i=v;i!=p;i=f[i])a[++tot]=i;
				reverse(a+pos+1,a+tot+1);
				for(int i=1;i<=n;i++)vis[i]=0;
				for(int i=1;i<=tot;i++)vis[a[i]]=1;
				for(int i=1;i<=tot;i++)sum[i]=dfs2(a[i],0)-1;
				for(int i=1;i<=tot;i++)sum[i]+=sum[i-1];
				for(int i=1;i<=tot;i++)for(int j=i;j<=tot;j++)for(int k=0;k<n;k++)dp[i][j][k]=0;
				for(int len=1;len<tot;len++)
				{
					for(int i=1;i+len-1<=tot;i++)
					{
						int j=i+len-1;
						for(int k=0;k<n;k++)
						{
							if(k+1<n&&sum[j]-sum[i-1]+j-i>=k+1)dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]);
							if(i>1)dp[i-1][j][k+1]=max(dp[i-1][j][k+1],dp[i][j][k]+w[k+1]);
							if(j<tot)dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+w[k+1]);
						}
					}
				}
				ans=max(ans,dp[1][tot][n-1]);
			}
		}
		cout<<ans<<'\n'; 
	}
	return 0;
}