/*
* Copyright (c) 2024 Emon Thakur
* All rights reserved.
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using minheap = priority_queue<long long, vector<long long>, greater<long long>>;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
#define ll long long
#define ld long double
#define MOD 1000000007
#define pie 2*(acos(0.0))
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
#define endl '\n'
#define lcm(a,b) (a*b)/(__gcd<ll>(a,b))
#define print(v) for(auto e:v) cout<<e<<" "; cout<<endl;
#define printp(v) for(auto e:v) cout<<e.first<<" "<<e.second<<endl;
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(v.rbegin(),v.rend())
#define life_is_a_race ios::sync_with_stdio(false); cin.tie(nullptr);
#define fr freopen("07input.txt","r",stdin);
ofstream file("07output.txt");
pair<ll,ll> dpup[200005],dpdown[200005];
ll apple[200005];
vector<ll> tr[200005];
void dpontree(ll node,ll starting,ll par)
{
if(apple[node]) dpdown[node] = {0,0};
else dpdown[node] = {-2,0};
for(auto e:tr[node])
{
if(e == par) continue;
dpontree(e,starting,node);
}
ll mxdif = 0 , sum = 0;
for(auto e:tr[node])
{
if(e == par) continue;
sum += dpdown[e].first;
mxdif = max(mxdif , dpdown[e].first - dpdown[e].second);
}
sum += (tr[node].size()-1)*2;
if(node == starting) sum += 2;
if(sum > 0) dpdown[node] = {sum , sum - mxdif -1};
}
void rerooting(ll node,ll par)
{
ll mxdif = -1, mxdif2 = -1, mxe = -1, mxe2 = -1,sum = 0;
for(auto e:tr[node])
{
if(e == par) continue;
sum += dpdown[e].first + 2;
if(dpdown[e].first-dpdown[e].second >= mxdif)
{
mxdif2 = mxdif;
mxe2 = mxe;
mxdif = dpdown[e].first - dpdown[e].second;
mxe = e;
}
else if(dpdown[e].first - dpdown[e].second >= mxdif2)
{
mxdif2 = dpdown[e].first - dpdown[e].second;
mxe2 = e;
}
}
sum += dpup[node].first;
if(dpup[node].first - dpup[node].second - 1 > mxdif)
{
mxdif2 = mxdif;
mxe2 = mxe;
mxdif = dpup[node].first - dpup[node].second - 1;
mxe = node;
}
else if(dpup[node].first - dpup[node].second - 1 > mxdif2)
{
mxdif2 = dpup[node].first - dpup[node].second - 1;
mxe2 = node;
}
for(auto e:tr[node])
{
if(e == par) continue;
if(e == mxe)
{
dpup[e].first = sum - dpdown[e].first;
dpup[e].second = dpup[e].first - mxdif2 - 2;
}
else
{
dpup[e].first = sum - dpdown[e].first ;
dpup[e].second = dpup[e].first - mxdif - 2;
}
rerooting(e,node);
}
}
void rerooting2(ll node,ll par)
{
for(auto e:tr[node])
{
if(e == par) continue;
ll sum = 0, mxdif = -1;
for(auto ee:tr[node])
{
if(ee == e || ee == par) continue;
sum += dpdown[ee].first + 2;
mxdif = max(mxdif , dpdown[ee].first - dpdown[ee].second);
}
mxdif = max(mxdif , dpup[node].first - dpup[node].second - 1);
sum += dpup[node].first;
dpup[e].first = sum+2;
dpup[e].second = dpup[e].first - mxdif - 2;
rerooting2(e,node);
}
}
void solve(int tc)
{
//cout<<"Case "<<tc<<": ";
ll n; cin >> n;
for(int i=1;i<=n;i++) cin>>apple[i];
ll u,v;
for(int i=0;i<n-1;i++)
{
cin >> u >> v;
tr[u].push_back(v);
tr[v].push_back(u);
}
ll starting = 0;
for(int i=1;i<=n;i++)
{
if(apple[i])
{
starting = i;
break;
}
}
if(!starting) {cout<<0<<endl; return;}
dpontree(starting,starting,0ll);
dpup[starting] = {0,0};
//rerooting(starting,starting,tr,apple,dpup,dpdown);
rerooting(starting,starting);
//for(int i=1;i<=n;i++) cout<<i<<" "<<dpup[i].first<<" "<<dpup[i].second<<" "<<dpdown[i].first<<" "<<dpdown[i].second<<endl;
ll ans = 1e9;
for(int i=1;i<=n;i++)
{
if(apple[i])
{
ans = min ({ans ,dpup[i].first + dpdown[i].second, dpup[i].second + dpdown[i].first });
}
}
cout<<ans<<endl;
//file<<ans<<endl;
for(int i=0;i<=n;i++)
{
dpup[i] = {0,0};
dpdown[i] = {0,0};
tr[i].clear();
}
}
int main()
{
life_is_a_race
//fr
int t=1;
cin>>t;
for(int i=1;i<=t;i++) solve(i);
}