#include <bits/stdc++.h>

#ifdef LOCAL
#include "template.cpp.h"
#else
#define debug(...)
#endif

//#define int long long
using namespace std;
#define cinv(v) for (auto &it:v) cin>>it;
#define coutv(v) for (auto &it:v) cout<< it<<' '; cout<<'\n';

const int N = 2e5 + 5;
vector<int> adj[N];
int n, ans, dist[N], node1, node2;
bool a[N];

void dfs(int now, int par) {
    for (auto &it: adj[now]) {
        if (it == par) continue;
        dist[it] = dist[now] + 1;
        dfs(it, now);
    }
}

bool dfs2(int now, int par) {
    dist[now] = 1;
    bool ret = a[now];
    int cnt = 0;
    for (auto &it: adj[now]) {
        if (it == par) continue;
        bool f = dfs2(it, now);
        ret |= f;
        dist[now] += dist[it];
        if (!f) cnt += dist[it];
    }
    if (ret || now == node1) ans -= 2 * cnt;
    return ret;
}

void reset() {
    ans = 0, node1 = node2 = 1;
    for (int i = 1; i <= n; ++i) adj[i].clear(), dist[i] = 0, a[i] = false;
}

void shelby() {
    reset();
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if (count(a, a + n + 1, true) < 2) {
        cout << "0\n";
        return;
    }
    dfs(1, -1);
    int now = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist[i] > now && a[i]) {
            now = dist[i];
            node1 = i;
        }
    }
    dist[node1] = 0;
    dfs(node1, -1);
    now = 0;
    for (int i = 1; i <= n; ++i) {
        if (dist[i] > now && a[i]) {
            now = dist[i];
            node2 = i;
        }
    }
    ans = 2 * n - 2 - now;
    dfs2(node1, -1);
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
//        cout << "Case " << _ << ": ";
        shelby();
    }
}