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

typedef long long ll;
const ll md = 1e9+7;
map<int,vector<int>>tree;
void fnd(int i,int vis[],int lv1[],int par[],int dp[],int ara[]){
vis[i]++;
if(ara[i])dp[i]=1;
for(auto it:tree[i]){
    if(!vis[it]){
            par[it]=i;
        lv1[it]=lv1[i]+1;
        fnd(it,vis,lv1,par,dp,ara);
        if(dp[it])dp[i]=1;
    }
}

}
void dfs(int i,int vis[],int tmp,int &ans,int dp[]){

vis[i]++;
for(auto it:tree[i]){
    if(!vis[it]&&it!=tmp&&dp[it]){
        ans+=2;
        dfs(it,vis,tmp,ans,dp);
    }
}
}
void solve() {
    tree.clear();
  int n;
  cin>>n;
  int ara[n+1];
  for(int i=1;i<=n;i++)cin>>ara[i];
  int dp[n+1]={0};
  int lv1[n+1]={0};
  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    tree[x].push_back(y);
    tree[y].push_back(x);
  }
  int vis[n+1]={0};
  int par[n+1]={0};
  fnd(1,vis,lv1,par,dp,ara);
  int mx=0;
  int j=1;
  for(int i=1;i<=n;i++){
        vis[i]=0;
        dp[i]=0;
    if(lv1[i]>=mx&&ara[i]){
        j=i;
        mx=lv1[i];
    }
  }
  int lv2[n+1]={0};
  par[j]=0;
  fnd(j,vis,lv2,par,dp,ara);
  mx=0;
  for(int i=1;i<=n;i++){
        vis[i]=0;
      if(lv2[i]>=mx&&ara[i]){
        j=i;
        mx=lv2[i];
    }
  }
  int x=j;
  vector<int>v;
  while(x!=0){
    v.push_back(x);
    x=par[x];
  }
  int ans=0;
  for(int i=v.size()-1;i>0;i--){
    dfs(v[i],vis,v[i-1],ans,dp);
  }
  if(v.size())
  ans+=v.size()-1;
  cout<<ans<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
     cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}