// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T &x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T &x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 160;
const ll INF = 1e18;
int n, a[N], ff[N][N], sz[N][N], dep[N][N];
ll dp[N][N][N][2][2];
vector <int> v[N];
void dfs(int rt, int x, int fa) {
	dep[rt][x] = dep[rt][fa] + 1;
	sz[rt][x] = 1;
	ff[rt][x] = fa;
	for (int i: v[x])
		if (i != fa) {
			dfs(rt, i, x);
			sz[rt][x] += sz[rt][i];
		}
}
void zhk() {
	ll ans = 0;
	read(n);
	F(i, 1, n + 1) v[i].clear();
	F(i, 1, n) read(a[i]), chkmax(ans, (ll) a[i]);
	F(i, 1, n) {
		int x, y; read(x), read(y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	F(i, 0, n)
		F(a, 1, n + 1)
			F(b, 1, n + 1)
				F(ta, 0, 1)
					F(tb, 0, 1)
						dp[i][a][b][ta][tb] = - INF;
	F(i, 1, n + 1) {
		dfs(i, i, 0);
	}
	F(i, 1, n)
		for (int j: v[i]) {
			dp[0][j][i][0][1] = 0;
			dp[0][j][i][1][0] = 0;
			dp[0][i][j][0][1] = 0;
			dp[0][i][j][1][0] = 0;
			for (int k: v[i])
				if (j != k) dp[0][j][k][0][0] = 0;
		}
	// vector <pair <int, int>> g;
	// F(i, 1, n + 1)
	// 	F(j, 1, n + 1)
	// 		g.emplace_back(i, j);
	// sort(all(g), [&] (pair <int, int> x, pair <int, int> y) {
	// 	return dep[x.first][x.second] < dep[y.first][y.second];
	// });
	F(i, 0, n - 1)
		F(a, 1, n + 1) F(b, 1, n + 1) F(ta, 0, 1) F(tb, 0, 1) if (dp[i][a][b][ta][tb] != - INF) {
			// debug << a << " " << b << " " << dp[i][a][b] << endl;
			// chkmax(ans, dp[i][a][b] + ::a[i + 1]);
			if (ta == 0) {
				chkmax(dp[i + 1][a][b][1][tb], dp[i][a][b][ta][tb] + ::a[i + 1]);
				for (int t: v[a])
					if (t != ff[b][a]) {
						chkmax(dp[i + 1][t][b][ta][tb], dp[i][a][b][ta][tb] + ::a[i + 1]);
					}
			}
			if (tb == 0) {
				chkmax(dp[i + 1][a][b][ta][1], dp[i][a][b][ta][tb] + ::a[i + 1]);
				for (int t: v[b])
					if (t != ff[a][b]) {
						chkmax(dp[i + 1][a][t][ta][tb], dp[i][a][b][ta][tb] + ::a[i + 1]);
					}
			}
			int w = n - sz[a][b] - sz[b][a] + ta + tb;
			if (w > i) {
				chkmax(dp[i + 1][a][b][ta][tb], dp[i][a][b][ta][tb]);
			}
			chkmax(ans, dp[i][a][b][ta][tb]);
		}
	F(a, 1, n + 1)
		F(b, 1, n + 1) {
			chkmax(ans, dp[n][a][b][1][1]);
			F(ta, 0, 1)
				F(tb, 0, 1)
					if (!ta || !tb)
						assert(dp[n][a][b][ta][tb] == - INF);
			// debug << a << " " << b << " " << dp[n][a][b][1][1] << endl;
		}
	// debug << dp[1]
	cout << ans << '\n';
}
signed main() {
	int _ = 1;
	cin >> _;
	while (_--) zhk();
	return 0;
}
/* why?
*/