#include <bits/stdc++.h>
using namespace std;
long long f[155][155][365], maxn[155][155][365], siz[155][155], pre[155][155];
vector<pair<int, int>> vv[155];
int n, qwe, a[155], cnt, sum[155];
int maxa, maxb;
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--) {
		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);
		}
		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);
			vv[0].push_back(make_pair(i, 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] = maxn[i][j][k] = -0x3f3f3f3f3f3f3f3f;
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			f[i][i][n - 1] = 0;
			for (int j = 0; j <= n - 1; j++) maxn[i][i][j] = 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;
				int prel = pre[l][r], prer = pre[r][l];
				for (int k = 0; k <= n - len; k++) {
					f[l][r][k] = max(f[l][r][k], maxn[prel][r][max(k + 1ll, siz[prel][l])] + a[(n - 1 - len) - k + len]);
				}
				for (int k = 0; k <= n - len; k++) {
					f[l][r][k] = max(f[l][r][k], maxn[l][prer][max(k + 1ll, siz[prer][r])] + a[(n - 1 - len) - k + len]);
//					cout << l << " " << r << " " << k << ' ' << f[l][r][k] << ' ' << len << "@\n";
				}
				for (int k = n; k >= 0; k--) {
					maxn[l][r][k] = max(maxn[l][r][k + 1], f[l][r][k]);
				}
			}
		}
		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				ans = max(ans, maxn[i][j][0]);
			}
		}
		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