#include <bits/stdc++.h>
using namespace std;
long long f[155][155][165], maxn[155][155][165];
int n, qwe, a[155], siz[155], cnt, sum[155];
vector<int> to[155], v, vv;
int maxa, maxb;
inline void dfs(int p, int q, int w) {
	if (w > maxa) {
		maxa = w, maxb = p;
	}
	for (int i : to[p]) {
		if (i != q) {
			dfs(i, p, w + 1);
		}
	}
}
inline void ddfs(int p, int q, int w) {
	vv.push_back(p);
	if (w > maxa) {
		maxa = w;
		v = vv;
	}
	for (int i : to[p]) {
		if (i != q) ddfs(i, p, w + 1);
	}
	vv.pop_back();
}
inline void getsiz(int p, int pp, int qq, int q, int name) {
	siz[name]++;
	for (int i : to[p]) {
		if (i != pp && i != qq && i != q) {
			getsiz(i, pp, qq, p, name);
		}
	}
}
signed main() {
//	freopen("length.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++) {
			cin >> p >> q;
			to[p].push_back(q), to[q].push_back(p);
		}
		maxa = -1;
		dfs(1, 0, 0);
		v.clear(), vv.clear();
		maxa = -1;
		vv.push_back(0);
		ddfs(maxb, 0, 0);
		cnt = v.size() - 1;
		v.push_back(0);
		for (int i = 1; i <= cnt; i++) {
			siz[i] = 0;
			getsiz(v[i], v[i - 1], v[i + 1], 0, i);
			siz[i]--;
			sum[i] = sum[i - 1] + siz[i];
		}
		for (int i = 1; i <= cnt; i++) {
			for (int j = 1; j <= cnt; j++) {
				for (int k = 0; k <= cnt + 3; k++) {
					f[i][j][k] = maxn[i][j][k] = -0x3f3f3f3f3f3f3f3f;
				}
			}
		}
		for (int i = 1; i < cnt; i++) {
			for (int j = 0; j <= max(siz[i], siz[i + 1]); j++) {
				f[i][i + 1][siz[i] + siz[i + 1] - j] = a[j + 1];
			}
			for (int j = sum[cnt]; j >= 0; j--) {
				maxn[i][i + 1][j] = max(maxn[i][i + 1][j + 1], f[i][i + 1][j]);
			}
		}
		for (int len = 3; len <= cnt; len++) {
			for (int l = 1, r = len; r <= cnt; l++, r++) {
				for (int k = sum[r] - sum[l - 1]; k >= 0; k--) {
					if (k >= siz[l]) f[l][r][k] = max(f[l][r][k], maxn[l + 1][r][k - siz[l]]);
					if (k >= siz[r]) f[l][r][k] = max(f[l][r][k], maxn[l][r - 1][k - siz[r]]);
					f[l][r][k] += a[sum[r] - sum[l - 1] - k + len - 1];
					maxn[l][r][k] = max(maxn[l][r][k + 1], f[l][r][k]);
				}
			}
		}
		cout << maxn[1][cnt][0] << "\n";
		for (int i = 1; i <= n; i++) to[i].clear();
	}
}
//1
//5
//1 7 3 5 4
//1 3
//2 3
//3 4
//4 5
//4 6