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

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

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

    vector<vector<array<int, 2>>> b(n + 2);
    vector len(n + 1, vector<int>(n + 1));

    int s = -1;
    auto dfs = [&](auto &&self, int u, int fa, int len1) -> void {
        for (int v : e[u]) {
            if (v == fa) {
                continue;
            }
            if (s < v) {
                b[len1 + 1].push_back({s, v});
                len[s][v] = len1 + 1;
            }
            self(self, v, u, len1 + 1);
        }
    };

    for (int i = 0; i <= n; ++i) {
        b[1].push_back({i, i});
    }
    for (int i = 0; i <= n; ++i) {
        s = i;
        dfs(dfs, i, -1, 1);
    }

    vector f(n + 1, vector(n + 1, vector<LL>(n + 1, -1)));

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            f[i][i][j] = 0;
        }
    }

    int cnt = 0;
    bool flag = false;
    int vv = -1;
    auto dfs1 = [&](auto &&self, int u, int fa) -> void {
        ++cnt;
        if (u == vv) {
            flag = true;
        }
        for (int v : e[u]) {
            if (v == fa) {
                continue;
            }
            self(self, v, u);
        }
    };

    auto myMx = [&](auto &x, const auto &y) {
        if (x < y) {
            x = y;
        }
    };

    for (int l = 1; l <= n; ++l) {
        for (auto [u, v] : b[l]) {
            vv = v;
            for (int vv : e[u]) {
                cnt = 0;
                dfs1(dfs1, vv, u);
                if (flag) {
                    flag = false;
                    continue;
                }
                int u1 = v, v1 = vv;
                if (u1 > v1) {
                    swap(u1, v1);
                }

                for (int i = 0; i <= n; ++i) {
                    if (n - cnt >= i && f[u][v][i] != -1) {
                        myMx(f[u1][v1][i + 1], f[u][v][i] + a[i]);
                    }
                }

                for (int i = 0; i <= n - 1; ++i) {
                    myMx(f[u1][v1][i + 1], f[u1][v1][i]);
                }
            }
            
            vv = u;
            for (int vv : e[v]) {
                cnt = 0;
                dfs1(dfs1, vv, v);
                if (flag) {
                    flag = false;
                    continue;
                }
                int u1 = u, v1 = vv;
                if (u1 > v1) {
                    swap(u1, v1);
                }

                for (int i = 0; i <= n; ++i) {
                    if (n - cnt >= i && f[u][v][i] != -1) {
                        myMx(f[u1][v1][i + 1], f[u][v][i] + a[i]);
                    }
                }

                for (int i = 0; i <= n - 1; ++i) {
                    myMx(f[u1][v1][i + 1], f[u1][v1][i]);
                }
            }
        }
    }

    LL ans = 0;
    for (int i=  0; i <= n; ++i) {
        for (int j = i; j <= n;++j) {
            for (int k = 0; k <= n; ++k) {
                ans = max(ans, f[i][j][k]);
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*
1
1
1000000000
1 2

1
5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
*/