#include <bits/stdc++.h>
using namespace std;
const int maxn = 160;
int T, n, a[maxn], dep[maxn], siz[maxn];
long long dp[maxn][maxn][maxn][4];
vector<int> g[maxn];
void dfs(int u, int pre) {
  siz[u] = 1, dep[u] = dep[pre] + 1;
  for(auto &v : g[u]) if(v != pre) dfs(v, u), siz[u] += siz[v];
}
void dfs2(int u, int pre, int x, int y) {
  if(u == y) {
    int mx = 0;
    for(int i = 0; i <= n; ++i) mx = max(mx, a[i]), dp[x][u][i][0] = mx;
    for(int i = 0; i <= siz[y] - 1; ++i) dp[x][u][i][1] = 0;
    for(int i = 0; i <= n - siz[u]; ++i) dp[x][u][i][2] = 0;
  } else {
    if(pre == y) dp[x][u][0][3] = 0;
    for (int i = 1; i <= n; ++i) {
      dp[x][u][i][0] = max(dp[x][u][i - 1][0], max(dp[x][u][i - 1][1], dp[x][u][i - 1][2]) + a[i]);
      dp[x][u][i][1] = dp[x][u][i - 1][3] + a[i];
      if (siz[y] - 1 >= i) dp[x][u][i][1] = max(dp[x][u][i][1], dp[x][u][i - 1][1]);
      dp[x][u][i][2] = dp[x][u][i - 1][3] + a[i];
      if (n - siz[u] >= i) dp[x][u][i][2] = max(dp[x][u][i][2], dp[x][u][i - 1][2]);
      dp[x][u][i][3] = max(dp[y][u][i - 1][3], dp[x][pre][i - 1][3]) + a[i];
      if (siz[y] - siz[u] - 1 >= i) dp[x][u][i][3] = max(dp[x][u][i][3], dp[x][u][i - 1][3]);
    }
  }
  for(auto &v : g[u]) if(v != pre) dfs2(v, u, x, y);
}
inline void solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  for(int i = 1; i <= n + 1; ++i) g[i].clear();
  for(int i = 1; i <= n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v), g[v].push_back(u);
  }
  for(int u = 1; u <= n + 1; ++u) for(int v = 1; v <= n + 1; ++v) for(int i = 0; i <= n; ++i) memset(dp[u][v][i], -0x3f, sizeof dp[u][v][i]);
  for(int u = 1; u <= n + 1; ++u) for(int i = 1; i <= n; ++i) dp[u][u][i][0] = 0;
  for(int u = 1; u <= n + 1; ++u) {
    dfs(u, 0);
    for(auto &v : g[u]) dfs2(v, u, u, v);
  }
  long long ans = 0;
  for(int u = 1; u <= n + 1; ++u) for(int v = 1; v <= n + 1; ++v) ans = max(ans, dp[u][v][n][0]);
  cout << ans << '\n';

//  for(int u = 1; u <= n; ++u) for(int v = 1; v <= n; ++v) {
//    cout << u << ' ' << v << ":\n";
//    for(int i = 0; i <= n; ++i) cout << (dp[u][v][i][0] < 0 ? -1 : dp[u][v][i][0]) << ' '; cout << '\n';
//    for(int i = 0; i <= n; ++i) cout << (dp[u][v][i][1] < 0 ? -1 : dp[u][v][i][1]) << ' '; cout << '\n';
//    for(int i = 0; i <= n; ++i) cout << (dp[u][v][i][2] < 0 ? -1 : dp[u][v][i][2]) << ' '; cout << '\n';
//    for(int i = 0; i <= n; ++i) cout << (dp[u][v][i][3] < 0 ? -1 : dp[u][v][i][3]) << ' '; cout << '\n';
//  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> T;
  while(T--) solve();
  return 0;
}