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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto& i : a) cin >> i;
        vector<vector<int>> g(n);
        for (int i = 0; i < n -1 ; ++i) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<array<array<int, 2>, 2>> dp(n);
        int ans = 1;
        auto dfs = [&](auto dfs, int u, int p) -> void {
            for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < 2; ++y) {
                    dp[u][x][y] = 1 + (x ? a[u] : 0) + (y ? -a[u] : 0);
                }
            }
            for (auto to : g[u]) {
                if (to == p) continue;
                dfs(dfs, to, u);
                for (int x = 0; x < 2; ++x) {
                    for (int y = 0; y < 2; ++y) {
                        ans = min(ans, dp[u][x][y] + dp[to][x ^ 1][y ^ 1]);
                    }
                }
                for (int x = 0; x < 2; ++x) {
                    for (int y = 0; y < 2; ++y) {
                        for (int i = 0; i < 2; ++i) {
                            for (int j = 0; j < 2; ++j) {
                                if (x & i) continue;
                                if (y & j) continue;
                                dp[u][x | i][y | j] = min(dp[u][x | i][y | j], dp[to][i][j] + 1 + (x ? a[u] : 0) + (y ? -a[u] : 0));
                            }
                        }
                    }
                }
            }
        };
        dfs(dfs, 0, -1);
        cout << ans << '\n';
    }
}