// #pragma GCC optimize("O3,unroll-loops,Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// template <class T> using ordered_set = tree<T, null_type,
//                          less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = (1e15)+5;
const int mod = 1000000007;
const double eps = 1e-6;
const int N = 200005;

void preprocess() {}

int a[N];
set<int> e[N];

int dist[N];

void dfs(int u, int p, int d) {
	dist[u] = d;
	for(int v : e[u]) if(v != p) dfs(v, u, d+1);
}

int diameter(int root, int n) {
	for(int i=0; i<=n; i++) dist[i] = inf;
	dfs(root, -1, 0);
	int far = root;
	for(int i=1; i<=n; i++) if(dist[i] != inf and dist[i] > dist[far]) far = i;
	dfs(far, -1, 0);
	int diam = 0;
	for(int i=1; i<=n; i++) if(dist[i] != inf) diam = max(diam, dist[i]);
	return diam;
}

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

	for(int i=0; i<=n; i++) e[i].clear();

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

	set<pii> st;
	for(int i=1; i<n; i++) {
		int u, v;
		cin >> u >> v;
		e[u].insert(v);
		e[v].insert(u);
	}

	if(on == 0) {
		cout << 0 << endl;
		return;
	}

	int edgecnt = n - 1;
	for(int i=1; i<=n; i++)
		st.insert({e[i].size(), i});

	while(st.size() and st.begin()->first == 1) {
		auto [cnt, u] = *st.begin();
		set<int> edges = e[u];
		
		if(a[u]) {
			st.erase({cnt, u});
			continue;
		}
		for(int v : edges) {
			st.erase({e[v].size(), v});
			e[v].erase(u);
			e[u].erase(v);
			st.insert({e[v].size(), v});
			edgecnt--;
		}
		st.erase({cnt, u});
	}

	// for(int i=1; i<=n; i++) {
	// 	cout << i << ' ' << a[i] << ": ";
	// 	for(int j : e[i]) cout << j << ' ';
	// 	cout << endl;
	// }
	int ans = edgecnt * 2 - diameter(on, n);
	cout << ans << endl;
}
    
int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess();

    int T = 1;
    cin >> T;

    for (int i = 1; i <= T; i++) {
        solve(i);
    }

    return 0;
}