#include <bits/stdc++.h>
using namespace std;
long long f[155][155][155][2][2], siz[155][155], pre[155][155];
vector<pair<int, int>> vv[155];
int n, qwe, a[155], cnt;
int maxa, maxb;
long long ans;
vector<int> to[155];
inline void gets(int p, int q, int name) {
	siz[name][p] = 1;
	for (int i : to[p]) {
		if (i != q) gets(i, p, name), siz[name][p] += siz[name][i];
	}
}
inline void finds(int p, int q, int w, int from) {
	pre[p][from] = q;
	if (p != from)vv[w].push_back(make_pair(p, from));
	for (int i : to[p]) {
		if (i != q) finds(i, p, w + 1, from);
	}
}
signed main() {
//	freopen("ex_length2.in", "r", stdin);
//	freopen("length.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> qwe;
	while (qwe--) {
		ans = -0x3f3f3f3f3f3f3f3f;
		cin >> n;
		n++;
		int p, q;
		for (int i = 1; i < n; i++) cin >> a[i];
		for (int i = 1; i < n; i++) {
			vv[i].clear();
			cin >> p >> q;
			to[p].push_back(q), to[q].push_back(p);
		}
		if (n == 2) {
			cout << a[1] << "\n";
			continue;
		}
		ans = a[1];
		for (int i = 2; i < n; i++) ans = max(ans, a[i] * 1ll);
		for (int i = 1; i <= n; i++) {
			for (int j : to[i]) {
				gets(j, i, i);
			}
		}
		for (int i = 1; i <= n; i++) {
			finds(i, 0, 0, i);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k <= n + 3; k++) {
					f[i][j][k][0][0] = f[i][j][k][0][1] = f[i][j][k][1][0] = f[i][j][k][1][1] =  -0x3f3f3f3f3f3f3f3f;
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			if (to[i].size() == 1) {
				for (int j : to[i]) {
					f[i][j][0][1][0] = f[j][i][0][0][1] = 0;
				}
			}
			for (int j : to[i]) {
				for (int k : to[j]) {
					if (i != k) {
						f[i][k][0][0][0] = 0;
					}
				}
			}
		}
		for (int len = 1; len < n; len++) {
			for (int i = 0; i < vv[len].size(); i++) {
				int l = vv[len][i].first, r = vv[len][i].second;
				for (int p = 0; p <= 1; p++) {
					for (int q = 0; q <= 1; q++) {
						int ups = n + 1 - siz[l][r] - siz[r][l];
						if (p == 1) ups += siz[r][l] - 1;
						if (q == 1) ups += siz[l][r] - 1;
//						for (int k = 0; k < n; k++) {
//							if (f[l][r][k][p][q] >= 0)cout << l << ' ' << r << ' ' << k  << ' ' << p << ' ' << q << ' ' << f[l][r][k ][p][q] << "\n";
//						}
						for (int k = 1; k < n; k++) {
							f[l][r][k][p][q] = max(f[l][r][k][p][q], f[l][r][k - 1][p][q]);
						}
						if (p == 0) {
							for (int pl : to[l]) {
								if (siz[r][pl] > siz[r][l]) continue;
								for (int kk = 1; kk <= ups; kk++) {
									f[pl][r][kk][1][q] = max(f[pl][r][kk][1][q], f[l][r][kk - 1][0][q] + a[kk]);
									f[pl][r][kk][0][q] = max(f[pl][r][kk][0][q], f[l][r][kk - 1][0][q] + a[kk]);
								}
							}
							for (int kk = 1; kk <= ups; kk++) {
								f[l][r][kk][1][q] = max(f[l][r][kk][1][q], f[l][r][kk - 1][0][q] + a[kk]);
							}
						}
						if (q == 0) {
							for (int pr : to[r]) {
								if (siz[l][pr] > siz[l][r]) continue;
								for (int kk = 1; kk <= ups; kk++) {
									f[l][pr][kk][p][1] = max(f[l][pr][kk][p][1], f[l][r][kk - 1][p][0] + a[kk]);
									f[l][pr][kk][p][0] = max(f[l][pr][kk][p][0], f[l][r][kk - 1][p][0] + a[kk]);
								}
							}
							for (int kk = 1; kk <= ups; kk++) {
								f[l][r][kk][p][1] = max(f[l][r][kk][p][1], f[l][r][kk - 1][p][0] + a[kk]);
							}
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k <= n; k++) {
					ans = max(ans, f[i][j][n - 1][1][1]);
				}
			}
		}
		cout << ans << "\n";
		for (int i = 1; i <= n; i++) to[i].clear();
	}
}
//1
//5
//1 5 5 3 10
//2 1
//3 1
//4 1
//5 4
//6 2

//1
//5
//1 7 3 5 4
//1 3
//2 3
//3 4
//4 5
//4 6