#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
#define int long long
const int inf = 10000000000000000;
int val[155][155];
vector<int>p[155];
int a[155],sz[155],vis[155],f[155];
int dp[155][155][155][2][2],ok[155],dis[155][155];
bool in[155][155][155];
int n;
void dfs(int now,int fa){f[now]=fa;for(auto x:p[now])if(x!=fa)dfs(x,now);}
void dfs1(int now,int fa,int& a){
	if(!ok[now])++a;
	for(auto x:p[now]){if(x!=fa and !ok[x])dfs1(x,now,a);}
}
bool cmp(pair<int,int>a,pair<int,int>b){return dis[a.first][a.second]<dis[b.first][b.second];}
void solve(){
	cin >> n;++n;
	for(int i = 1;i<n;i++)cin >> a[i];
//	cout << 111 << endl;
	for(int i =0;i<=n;i++)p[i].clear();
	for(int i =0;i<=n;i++)for(int j =0;j<=n;j++)for(int k = 0;k<=n;k++)in[i][j][k] = 0;
	for(int i= 1;i<=n;i++)for(int j =0;j<=n;j++)for(int k  =0;k<=n;k++){
		for(int l =0;l<2;l++){
			for(int d=0;d<2;d++){
				dp[i][j][k][l][d]=-inf;
			}
		}
	}
	for(int i =1;i<n;i++){
		int a,b;cin >> a >> b;
		p[a].push_back(b),p[b].push_back(a); 
	}
	for(int i = 1;i<=n;i++){
		dfs(i,i);
		vector<int>p;
	//	for(int j = 1;j<=n;j++)cout << f[j] <<' ';cout << endl;
		//continue;
		for(int j = 1;j<=n;j++){
			p.clear();
			int now = j;
			while(now!=i){
			//	cout <<" " << now << endl;
				p.push_back(now),now = f[now];
			}
			p.push_back(now);
			dis[i][j]=p.size();
			for(int k = 1;k<=n;k++)ok[k] =0 ;
			for(auto x:p)ok[x]=1,in[i][j][x]=1;
			val[i][j]=dis[i][j];
			for(int k = 1;k+1<p.size();k++){
				dfs1(p[k],p[k],val[i][j]);
			}
		}
	}
//	for(int i = 1;i<=n;i++){
//		for(int j = 1;j<=n;j++){
//			cout << val[i][j] << " ";
///		}
//		cout << endl;
/////	}
	//return;
	//不包含端点的路径和
	vector<pair<int,int> >s;
	for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++)s.push_back({i,j});
	sort(s.begin(),s.end(),cmp); 
	for(int i = 1;i<=n;i++)dp[i][i][0][1][1] = 0;
	int ans = 0;
	for(int ii =0;ii<s.size();ii++){
		int x = s[ii].first,y = s[ii].second;
		for(int k =0;k<=min(val[x][y],n-1);k++){
			ans=max(ans,dp[x][y][k][1][1]);
		//	cout << " " << x <<" " << y <<" " << k << " " << dp[x][y][k][1][1] << endl;
			for(int i =0;i<2;i++){
				for(int j =0;j<2;j++){
					int v = dp[x][y][k][i][j];
					if(i == 1){
						//拓展一端
						for(int a:p[x]){
							if(in[x][y][a])continue;
							dp[a][y][k][0][j] = max(dp[a][y][k][0][j],v);
						} 
					}
					if(j == 1){
						for(int a:p[y]){
							if(in[x][y][a])continue;
							dp[x][a][k][i][0] = max(dp[x][a][k][i][0],v);
						}
					}
					if(i == 0){
						//确定权值
						if(k+1<=val[x][y])dp[x][y][k+1][1][j]=max(dp[x][y][k+1][1][j],v+a[k+1]); 
					}
					if(j == 0){
						if(k+1<=val[x][y])dp[x][y][k+1][i][1]=max(dp[x][y][k+1][i][1],v+a[k+1]);
					}
					//往后走一步
					if(k+1<=val[x][y])dp[x][y][k+1][i][j]=max(dp[x][y][k+1][i][j],v); 
				}
			}
		}
	}
	cout << ans << endl; 
}
signed main(){
//	freopen("length.in","r",stdin);
//	freopen("length.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin >> t;
	while(t--)solve();
	return 0;
}/*
1
4
1 1 5 4
1 2
2 3
2 4
3 5
*/