#include<bits/stdc++.h>
using namespace std;
 
#define ll                      long long int
#define lld                     long double
//Ordered set(tree)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set             tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define multi_ordered_set       tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define mxheap                  priority_queue<ll>
#define mnheap                  priority_queue<ll, vector<ll>, greater<ll>>
#define mxheap2                 priority_queue<pair<ll,ll>>
#define mnheap2                 priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>
//Macros
#define FIO                     ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(NULL);
#define TC(t)                   int t; cin >> t; for(int i = 1; i <= t; i++)
#define ini(x, y)               memset(x, y, sizeof(x))
#define loop(i, a, b)           for(ll i = a; i <= b; i++)
#define loop2(i, b, a)          for(ll i = b; i >= a; i--)
#define pn                      cout << "NO\n";
#define py                      cout << "YES\n";
#define ed                      cout << "\n";
#define vrev(v)                 reverse(v.begin(),v.end());
#define vsort(v)                sort(v.begin(),v.end());
#define uni(v)                 v.erase(unique(v.begin(), v.end()), v.end()); // last it is like e set
#define vlowerB(v,x)            lower_bound(v.begin(), v.end(), x); 
#define vupperB(v,x)            upper_bound(v.begin(), v.end(), x); 
#define bits(x)                 __builtin_popcountll(x)
#define zrbits(x)               __builtin_ctzll(x)
//Constants
const ll M = 1e9 + 7;
const ll N = 2e5 + 5;
ll POW(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans = (ans * a) % M; a = (a * a) % M; b >>= 1; } return ans; }
/*  Contest time:
    1. Check it is binary searce or not.
    2. DP or not.
    3. Segment Tree of not
    4. Hash or not.
    5. Number theory   
*/

bool a[N];
set < int > g[N];

void dfs(int node){
    if(g[node].size() > 1 || a[node] == 1) return;
    for(auto u : g[node]){
        g[u].erase(node); g[node].erase(u);
        dfs(u);
    }
}
bool vis[N];

int dfs2(int node){
    int c = 1;
    vis[node] = 1;
    if(g[node].size() > 2 || a[node] == 1 ) {
        vis[node] = 0;
        return 1;
    }
    for(auto u : g[node]){
        if(vis[u]) continue;
        c += dfs2(u);
    }
    return c;
}

void solve(){
    int n; cin >> n;
    int c = 0;
    loop(i, 1, n) {
        cin >> a[i];
        if(a[i] == 1) c++;
        g[i].clear();
    }
    if(c <= 1){
        cout << "0\n"; return;
    }
    loop(i, 2, n){
        int x, y; cin >> x >> y;
        g[x].insert(y); g[y].insert(x);
    }
    loop(i, 1, n){
        vis[i] = 0;
        if(g[i].size() == 1 && a[i] == 0) dfs(i);
    }
    vector < int > v, vv;
    int x = n-1;
    loop(i, 1, n){
        if(g[i].empty()) x--;
        else if(g[i].size() == 1){
            //cout << i << " ";
            v.push_back(i);
            a[i] = 0;
        }
    }
    for(auto u : v) vv.push_back(dfs2(u)-1);
    v = vv;
    vsort(v); vrev(v);
    //for(auto u : v) cout << u << " "; ed
    x *= 2;
    //cout << x; ed
    if(c == 2) cout << x - v[0];
    else cout << x - v[0] - v[1];
    ed
}
 
int main(){
    FIO
    TC(t) 
    solve();
    return 0;
}