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

constexpr LL INF = 1e18;

void solve() {
    int n;
    cin >> n;
    vector<LL> 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);
    }

    int tot = n + 1;
    for (int i = 0; i <= n; ++i) {
        if (e[i].size() == 1) {
            e.push_back({});
            e[i].push_back(tot);
            e[tot].push_back(i);
            tot++;
        }
    }

    vector dis(tot, vector<int>(tot, -1));


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

    for (int i = 0; i < tot; ++i) {
        s = i;
        dfs(dfs, i, -1, 0);
    }

    sort(b.begin(), b.end());

    vector f(tot, vector(tot, vector<LL>(tot, -INF)));

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

    LL ans = 0;
    for (auto [len, x, y] : b) {
        if (len == 1) {
            continue;
        }
        if (len == 2) {
            f[x][y][0] = 0;
        }
        
        int cnt = 0;
        bool flag = false;
        auto dfs = [&](auto &&self, int u, int fa) -> void {
            for (int v : e[u]) {
                if (v == y) {
                    flag = true;
                    continue;
                }
                if (v == fa) {
                    continue;
                }
                if (v <= n) {
                    ++cnt;
                }
                self(self, v, u);
            }
        };

        for (int v : e[x]) {
            cnt = 0;
            dfs(dfs, v, x);
            if (flag) {
                break;
            }
        }

        auto update = [&](int x, int y, int z) {
            for (int p : e[x]) {
                int q = y;
                if (p > q) {
                    swap(p, q);
                }

                if (dis[p][q] != len + 1) {
                    continue;
                }

                myMx(f[p][q][z + 1], f[x][y][z] + a[z]);
            }
        };

        for (int i = 0; i <= cnt; ++i) {
            if (i) {
                myMx(f[x][y][i], f[x][y][i - 1]);
            }
            myMx(ans, f[x][y][i]);

            update(x, y, i);
            update(y, x, i);
        }
    }
    cout << ans << '\n';
}

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