///**Bismillahir Rahmanir Raheem**
///** Mizanul Hoque **
///** IIUC **
/// ###############################
#include <bits/stdc++.h>
using namespace std;
/// POLICY BASED DATA STRUCTURE..
/// order_of_key return number of element which are strictly greater/smaller than x..
/// find_by_order return ans iterator corresponding to the xth position of the set..
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define faster \
ios_base::sync_with_stdio(false); \
cin.tie(NULL)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define sz(n) (int)(n).size()
#define eps 1e-10
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define max3(a, b, c) max(c, max(a, b))
#define max4(a, b, c, d) max(d, max(c, max(a, b)))
#define pi 2 * acos(0) /// acos(-1.0)
#define deg_to_rad(x) ((x) * ((2 * acos(0)) / 180.0))
#define rad_to_deg(x) ((x) * (180.0 / (2 * acos(0))))
#define fi first
#define sc second
#define mp make_pair
#define __lcm(a, b) (a / __gcd(a, b) * b)
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int M = 1e9 + 7;
const int N = 200020;
// ll n,m,i,k,h;
vector<ll> prime_divisor[N];
int vis[N];
vector<int> edge[N];
bool cmp(pair<ll, ll> p1, pair<ll, ll> p2)
{
return p1.fi < p2.fi;
}
int height[N];
int dep[N];
int last[N];
ll a[N];
int siz[N];
ll ans = 0;
void dfs(int u, int par)
{
last[u] = (a[u] == 1);
siz[u] = 1;
for (auto v : edge[u])
{
if (v == par)
continue;
dfs(v, u);
last[u] += last[v];
// last[u] += (a[v] == 1);
siz[u] += siz[v];
}
}
void dfs1(int u, int par)
{
height[u] = 0;
vector<int> vec;
if (last[u] == 0)
{
ans -= (siz[u] * 2);
}
else
{
for (auto v : edge[u])
{
if (v == par)
continue;
if (last[v] == 0)
{
ans -= (siz[v] * 2);
continue;
}
dfs1(v, u);
vec.pb(height[v]);
height[u] = max(height[u], height[v] + 1);
}
sort(all(vec));
if (sz(vec) == 0)
{
dep[u] = 0;
}
else if (sz(vec) == 1)
{
dep[u] = vec[sz(vec) - 1] + 1;
}
else
{
dep[u] = vec[sz(vec) - 1] + vec[sz(vec) - 2] + 2;
}
}
}
void solve()
{
ll i, j, k, n, m, p, q, x, y, z, u, v, l, r, mod = 1e9 + 7, mx, mn, mx1, mn1, cnt1, cnt;
cin >> n;
int pos = -1;
cnt=0;
for (i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] == 1)
{
cnt++;
pos = i;
}
}
for (i = 0; i < n - 1; i++)
{
cin >> u >> v;
edge[u].pb(v);
edge[v].pb(u);
}
if (pos == -1)
{
cout << 0 << endl;
}
else if(cnt==1)
{
cout<<0<<endl;
}
else
{
dfs(pos, -1);
ans = 0;
ans = (n - 1) * 2;
// cout<<ans<<endl;
dfs1(pos, -1);
int mxx = 0;
for (i = 1; i <= n; i++)
{
mxx = max(mxx, dep[i]);
}
ans -= mxx;
cout << ans << endl;
}
for (i = 1; i <= n; i++)
{
edge[i].clear();
dep[i]=0;
}
}
int main()
{
faster;
ll tc = 1;
cin >> tc;
for (ll t = 1; t <= tc; t++)
{
/// cout<<"Case "<<t<<": ";
solve();
}
return 0;
}