#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 1e15;

int pathLength[155][155];
int inPath[155][155][155];
int freeEdge[155][155];
lint dp[155][155][155][2][2];

void chmax(lint &a, lint b) {
  a = max(a, b);
}

void Main() {
  int N;
  cin >> N;
  vector<lint> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  vector<vector<int>> adj(N + 1);
  for (int i = 0; i < N; i++ ){
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  for (int i = 0; i <= N + 3; i++) {
    for (int j = 0; j <= N + 3; j++) {
      freeEdge[i][j] = 0;
      pathLength[i][j] = 0;
      for (int k = 0; k <= N + 3; k++) {
        inPath[i][j][k] = 0;
        for (int a = 0; a < 2; a++) {
          for (int b = 0; b < 2; b++) {
            dp[i][j][k][a][b] = -INF;
          }
        }
      }
    }
  }

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
      const auto Dfs = [&](const auto &self, int u, int p) -> bool {
        if (u == j) {
          inPath[i][j][u] = 1;
          return true;
        }
        for (auto v : adj[u]) {
          if (v != p) {
            if (self(self, v, u)) {
              pathLength[i][j] += 1;
              inPath[i][j][u] = 1;
              return true;
            }
          }
        }
        return false;
      };
      Dfs(Dfs, i, -1);
      const auto Sub = [&](const auto &self, int u, int p) -> int {
        int res = 1;
        for (auto v : adj[u]) {
          if (v != p) {
            res += self(self, v, u);
          }
        }
        return res;
      };
      for (int k = 0; k <= N; k++) if (k != i && k != j && inPath[i][j][k]) {
        for (auto x : adj[k]) {
          if (!inPath[i][j][x]) {
            freeEdge[i][j] += Sub(Sub, x, k);
          }
        }
      }
    }
  }

  for (int i = 0; i <= N; i++) {
    dp[0][i][i][1][1] = 0;
  }

  lint ans = -INF;
  for (int pos = 0; pos <= N; pos++) {
    for (int dx = 1; dx >= 0; dx--) {
      for (int dy = 1; dy >= 0; dy--) {
        for (int x = 0; x <= N; x++) {
          for (int y = 0; y <= N; y++) {
            if (dp[pos][x][y][dx][dy] < 0) {
              continue;
            }
            if (pos == N && dx == 1 && dy == 1) {
              ans = max(ans, dp[pos][x][y][dx][dy]);
            }
            if (pos == N) {
              continue;
            }
            lint val = dp[pos][x][y][dx][dy];
            if (dx == 0) {
              chmax(dp[pos + 1][x][y][1][dy], val + A[pos]);
            } else {
              for (auto nxtx : adj[x]) if (!inPath[x][y][nxtx]) {
                chmax(dp[pos][nxtx][y][0][dy], val);
              }
            }
            if (dy == 0) {
              chmax(dp[pos + 1][x][y][dx][1], val + A[pos]);
            } else {
              for (auto nxty : adj[y]) if (!inPath[x][y][nxty]) {
                chmax(dp[pos][x][nxty][dx][0], val);
              }
            }
            int unused = pathLength[x][y] - (dx == 0) - (dy == 0) + freeEdge[x][y];
            unused -= pos;
            if (unused >= 1) {
              chmax(dp[pos + 1][x][y][dx][dy], val);
            }
          }
        }
      }
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int T;
  cin >> T;
  while (T--) {
    Main();
  }
  return 0;
}