#include<bits/stdc++.h>
using namespace std;

#define print(a) for(auto x:a)cout<<x<<' ';cout<<'\n';
#define debug(x) cout<<#x<<" "<<x<<'\n'
#define int   long long int

const int M = 1e9 + 7;
const int N = 2e5 + 10;

int anc[N][25],d[N];
vector<int>g[N];
void dfs(int u,int p=-1){
anc[u][0]=p;
for(int i=1;i<19;i++)
    anc[u][i]=~anc[u][i-1]?anc[anc[u][i-1]][i-1]:-1;
for(int v:g[u]){
    if(v==p)continue;
    d[v]=d[u]+1;
    dfs(v,u);
}
}
int lca(int u,int v){
if(d[u]<d[v])
    swap(u,v);
for(int i=18;~i;i--)
    if(d[u]-(1<<i)>=d[v])
    u=anc[u][i];
if(u==v)
    return u;
for(int i=18;~i;i--)
    if(anc[u][i]^anc[v][i])
    u=anc[u][i],v=anc[v][i];
return anc[u][0];
}
int dist(int u, int v){
    return d[u]+d[v]-2*d[lca(u,v)];
}

int a[N], tot[N];

void dfs1(int u, int p = -1){
   for(auto v : g[u]){
      if(v == p)continue;
      dfs1(v,u);
     // cout << u <<"->"<< v<<'\n';
      if(tot[v] > 0)tot[u] += (tot[v] + 2);
      else if(a[v]) tot[u] += 2;
   }
}

void solve(){
    int n; cin >> n;
    for(int i = 0; i <= n; i++){
      g[i].clear();a[i] = 0;tot[i] = 0;
    }

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

    for(int i = 1; i < n; i++){
      int u, v; cin >> u >> v, u--, v--;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    dfs(0);

    if(x == -1){
      cout << 0 << '\n';return;
    }
    int y = x;

    for(int i = 0; i < n; i++){
      if(a[i] == 0)continue;
      if(dist(x, i) > dist(x, y)) y = i;
    }
    for(int i = 0; i < n; i++){
      if(a[i] == 0)continue;
      if(dist(y,i) > dist(y, x)) x = i;
    }

    if(x == y){
      cout << 0 << '\n';return;
    }

    dfs1(x);
   //for(int i = 0; i < n; i++)cout << tot[i] << ' ';cout << '\n';
    int res = tot[x] -  dist(x, y);
    cout << res << '\n';
}

signed main() {
   ios_base::sync_with_stdio (0);
   cin.tie (0);

   int t = 1;   cin >> t;
   for (int tc = 1; tc <= t; tc++) {
      //cout<<"Case "<<tc<<": ";
      solve();
   }
   return 0;
}