#include <bits/stdc++.h>
using namespace std;
#define int long long
int n; vector<int> vecs[155];
int dp[155][155][155][2][2],a[155],sws[155][155],dep[155][155];
inline void foo(int& x,int y) {x = (x>y)?(x):(y);} //for convince
void dfs(int now,int pa,int c) {
	dep[c][now] = dep[c][pa]+1; sws[c][now] = 1;
	for(auto v:vecs[now]) {
		if(v == pa) continue; dfs(v,now,c);
		sws[c][now] += sws[c][v];
	}
}
void solve() { //damn, multitest???!
	cin >> n; n++; for(int i = 1; i < n; i++) {cin >> a[i]; vecs[i].clear();} vecs[n].clear();
	for(int i = 1; i < n; i++) {
		int u,v; cin >> u >> v;
		vecs[u].push_back(v); vecs[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) dfs(i,0,i);
	for(int k = 0; k < n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
		dp[k][i][j][0][0] = dp[k][i][j][0][1] = dp[k][i][j][1][0] = dp[k][i][j][1][1] = -0x3f3f3f3f3f3f3f3f;
	}
	for(int i = 1; i <= n; i++) {
		for(auto v:vecs[i]) {
			dp[0][i][v][1][0] = dp[0][v][i][0][1] = 0;
			for(auto w:vecs[i]) if(v != w) dp[0][w][v][0][0] = 0;
		}
	}
	for(int k = 0; k < n-1; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				foo(dp[k+1][i][j][1][1],dp[k][i][j][1][1]); //ci && cj
				//!ci && cj
				foo(dp[k+1][i][j][1][1],dp[k][i][j][0][1]+a[k+1]); 
				if(k < n+1-sws[j][i]) foo(dp[k+1][i][j][0][1],dp[k][i][j][0][1]);
				for(auto v:vecs[i]) {
					if(dep[v][j] < dep[i][j]) continue;
					foo(dp[k+1][v][j][0][1],dp[k][i][j][0][1]+a[k+1]);
				}
				//ci && !cj
				foo(dp[k+1][i][j][1][1],dp[k][i][j][1][0]+a[k+1]); 
				if(k < n+1-sws[i][j]) foo(dp[k+1][i][j][1][0],dp[k][i][j][1][0]);
				for(auto v:vecs[j]) {
					if(dep[v][i] < dep[j][i]) continue;
					foo(dp[k+1][i][v][1][0],dp[k][i][j][1][0]+a[k+1]);
				}
				//!ci && !cj
				foo(dp[k+1][i][j][1][0],dp[k][i][j][0][0]+a[k+1]);
				foo(dp[k+1][i][j][0][1],dp[k][i][j][0][0]+a[k+1]);
				if(k < n+2-sws[i][j]-dep[i][j]-sws[j][i]-dep[j][i]) foo(dp[k+1][i][j][0][0],dp[k][i][j][0][0]);
				for(auto v:vecs[i]) {
					if(dep[v][j] < dep[i][j]) continue;
					foo(dp[k+1][v][j][0][0],dp[k][i][j][0][0]+a[k+1]);
				}
				for(auto v:vecs[j]) {
					if(dep[v][i] < dep[j][i]) continue;
					foo(dp[k+1][i][v][0][0],dp[k][i][j][0][0]+a[k+1]);
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) for(int ci = 0; ci < 2; ci++) 
		for(int cj = 0; cj < 2; cj++) ans = max(ans,dp[n-1][i][j][ci][cj]);
	}
	printf("%lld\n",ans);
	for(int i = 1; i <= n; i++) vecs[i].clear();
}
signed main() {
	//freopen("length.in","r",stdin);
	//freopen("length.out","w",stdout);
	cin.tie(0)->sync_with_stdio(false);
	int T; cin >> T; while(T--) solve();
	return 0;
}