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

const int N = 155, D = 9, M = 4;
vector<int> edges[N];

using ll = long long;
int a[N];
int sz[N][N], pre[N][N];
ll dp[N][N][N][M];

inline ll smx(ll &a, ll b) {
    return a = max(a, b);
}

inline int tmx(int &a, int &b) {
    if(a < b)   swap(a, b);
    return a;
}
inline ll tmx(ll &a, ll &b) {
    if(a < b)   swap(a, b);
    return a;
}

void solve()
{
    int n;
    cin >> n;
    n++;
    for(int i = 1; i <= n; i++) {
        if(i != n) cin >> a[i];
        edges[i].clear();
    }

    int u, v;
    for(int i = 1; i < n; i++) {
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    auto dfs = [&](auto self, int s, int u, int f) -> void {
        sz[s][u] = 1;
        for(int nxt: edges[u])  if(nxt != f) {
            pre[s][nxt] = u;
            self(self, s, nxt, u);
            sz[s][u] += sz[s][nxt];
        }
    };

    for(int i = 1; i <= n; i++) dfs(dfs, i, i, i);
    // cout << "::0" << endl;

    const ll INF = 1e15;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 0; k <= n; k++) {
                for(int u = 0; u < M; u++)  dp[i][j][k][u] = -INF;
            }
        }
    }
    // cout << "::1" << endl;

    for(int i = 1; i <= n; i++) {
        dp[i][i][1][0] = 0;
        for(int j: edges[i]) {
            if(i < j)   dp[i][j][1][1] = 0;
            else    dp[j][i][1][1] = 0;
        }

        for(int j: edges[i]) {
            for(int k: edges[i])    if(j != k) {
                tmx(k, j);
                dp[j][k][1][3] = 0;
            }
        }
    }
    // cout << "::1" << endl;

    for(int t = 1; t < n; t++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) if(i != j) {
                for(int m = 0; m < M; m++) {
                    if(m == 0)  {
                        smx(dp[i][j][t+1][m], dp[i][j][t][m]);
                    } else if(m == 1) {
                        smx(dp[i][j][t+1][0], dp[i][j][t][m] + a[t]);
                        for(int nxt: edges[j])  if(nxt != pre[i][j])  smx(dp[i][nxt][t+1][m], dp[i][j][t][m] + a[t]);
                        int rem = n - 1 - sz[i][j] - t + 1;
                        if(rem) smx(dp[i][j][t+1][m], dp[i][j][t][m]);
                    } else if(m == 2) {
                        smx(dp[i][j][t+1][0], dp[i][j][t][m] + a[t]);
                        for(int nxt: edges[i])  if(nxt != pre[j][i])  smx(dp[nxt][j][t+1][m], dp[i][j][t][m] + a[t]);
                        int rem = n - 1 - sz[j][i] - t + 1;
                        if(rem) smx(dp[i][j][t+1][m], dp[i][j][t][m]);
                    } else {
                        smx(dp[i][j][t+1][1], dp[i][j][t][m] + a[t]);
                        smx(dp[i][j][t+1][2], dp[i][j][t][m] + a[t]);

                        for(int nxt: edges[j])  if(nxt != pre[i][j])    smx(dp[i][nxt][t+1][m], dp[i][j][t][m] + a[t]);
                        for(int nxt: edges[i])  if(nxt != pre[j][i])    smx(dp[nxt][j][t+1][m], dp[i][j][t][m] + a[t]);
                        int rem = n - 1 - sz[j][i] - sz[i][j] - t + 1;
                        if(rem)    smx(dp[i][j][t+1][m], dp[i][j][t][m]);
                    }
                }
            }
        }
    }

    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            smx(ans, dp[i][j][n][0]);
        }
    }
    printf("%lld\n", ans);
}

int main() 
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)  solve();

    return 0;
}