#include<bits/stdc++.h>
using namespace std;
const long long M=3e5+10,MOD=1000000000;
typedef long long ll;
vector<int>edge[M];
int level[M];
int d[M];
ll sum[M];
int arr[M];
void dfs1(int x,int p){
    for(int u:edge[x]){
        if(u!=p){
            d[u]=d[x]+1;
            dfs1(u,x);
        }
    }
}
void dfs(int x,int p){
    for(int u:edge[x]){
        if(u!=p){
            d[u]=d[x]+1;
            dfs(u,x);
        }
    }
    level[p]+=level[x];
    sum[p]+=sum[x]+(2*min(1,level[x]));
    
}
void clear_edge(int n){
    for(int i=0;i<=n;i++){
        edge[i].clear();
        sum[i]=0;
        level[i]=0;
        d[i]=0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
     int n;
     cin>>n;
     int cnt=0;
     clear_edge(n);
     int node=1;
     for(int i=1;i<=n;i++){
        cin>>level[i];
        cnt+=level[i];
        arr[i]=level[i];
        if(arr[i])node=i;
     }
     for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
     }
     if(cnt<=1){
        cout<<0<<"\n";
        continue;
     }
     dfs(node,0);
     int cur=1;
     int mx_dis=0;
     for(int i=1;i<=n;i++){
        if(mx_dis<d[i] && arr[i]){
            mx_dis=d[i];
            cur=i;
        }
        d[i]=0;
     }
     dfs1(cur,0);
     int maximum_dis=0;
     for(int i=1;i<=n;i++)if(arr[i])maximum_dis=max(maximum_dis,d[i]);
     cout<<sum[node]-maximum_dis<<"\n";
    


    }




    
   
   return 0;
 
}