#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000013;
const int P=998244353;
int dp[N][4],a[N];
int ans;
vector<int>mp[N];

void dfs(int x,int fa) {
    int nw[4]={1,1-a[x],1+a[x],1};
    int g[4]={1,1-a[x],1+a[x],1};
    for(auto i:mp[x])if(i^fa) {
        dfs(i,x);
        //nw+i->ans
        for(int j:{0,1,2,3})ans=min(ans,nw[3^j]+dp[i][j]);
        //{x}+nw->nw
        nw[0]=min(nw[0],dp[i][0]+g[0]);
        nw[1]=min({nw[1],dp[i][1]+g[0],dp[i][0]+g[1]});
        nw[2]=min({nw[2],dp[i][2]+g[0],dp[i][0]+g[2]});
        nw[3]=min({nw[3],dp[i][3]+g[0],dp[i][0]+g[3],dp[i][1]+g[2],dp[i][2]+g[1]});
    }
    for(int j:{0,1,2,3})dp[x][j]=nw[j];
    ans=min(ans,dp[x][3]);
}

void solve(){
    ans=1e9;
    int n;cin>>n;
    for(int i=1;i<=n;i++)mp[i].clear();
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=0;j<4;j++)dp[i][j]=1e9;
    for(int i=1,x,y;i<n;i++)cin>>x>>y,mp[x].push_back(y),mp[y].push_back(x);
    dfs(1,0);
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)solve();
}