#include<bits/stdc++.h>
#define int long long
using namespace std;
int dep[155],dp[155][155][155],T,n,h[155],u,v,w[155],f[155];
int siz[155],num[155][155],deg[155],cnt,dis[155][155];
struct edge{int v,nxt;}e[305];vector<pair<int,int> >g[155];
void add(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void dfs(int u,int fa,int s)
{
	dis[s][u]=dis[s][fa]+1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u,s);
	}
}
void dfs2(int u,int fa)
{
	dep[u]=dep[fa]+1;siz[u]=1;f[u]=fa;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs2(v,u);siz[u]+=siz[v];
	}
}
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;
		for(int i=1;i<n;i++)
		{
			cin>>u>>v;
			add(u,v);add(v,u);
		}
		for(int i=0;i<=n;i++)g[i].clear();
		for(int i=1;i<=n;i++)
		{
			dis[i][0]=-1;dfs(i,0,i);
			for(int j=1;j<=n;j++)g[dis[i][j]].emplace_back(make_pair(i,j));
		}
		dfs2(1,0);
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=0;k<n;k++)dp[i][j][k]=-0x3f3f3f3f3f3f3f3f;
		for(int i=1;i<=n;i++)dp[i][i][0]=0;
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<g[i].size();j++)
			{
				int u=g[i][j].first,v=g[i][j].second;
				for(int k=0;k<n;k++)
				{
					if(k+1<n)dp[u][v][k+1]=max(dp[u][v][k+1],dp[u][v][k]);
					for(int p=h[u];p;p=e[p].nxt)
					{
						int now=n-1-(dep[e[p].v]>dep[u]?siz[e[p].v]:n-siz[u]);
						if(dis[e[p].v][v]==i+1&&k<=now)dp[e[p].v][v][k+1]=max(dp[e[p].v][v][k+1],dp[u][v][k]+w[k+1]);
					}
					for(int p=h[v];p;p=e[p].nxt)
					{
						int now=n-1-(dep[e[p].v]>dep[v]?siz[e[p].v]:n-siz[v]);
						if(dis[u][e[p].v]==i+1&&k<=now)dp[u][e[p].v][k+1]=max(dp[u][e[p].v][k+1],dp[u][v][k]+w[k+1]);
					}
				}
			}
		}
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans=max(ans,dp[i][j][n-1]);
		cout<<ans<<'\n'; 
	}
	return 0;
}