厦门2019 J

/**
 *    author:  MySakure
 *    created: 21.10.2019 11:22:49
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
const int inf=1e9;
int dp[maxn][2],t,n,v[maxn],ans;
vector<int>g[maxn];
//0 最大值
//1 最小值
void dfs(int u,int fa){
    dp[u][0]=min(dp[u][0],1-v[u]);
    dp[u][1]=min(dp[u][1],1+v[u]);
    if(fa!=-1){
        ans=min(ans,dp[fa][0]+1+v[u]);
        ans=min(ans,dp[fa][1]+1-v[u]);
    }
    for(int i=0;i<signed(g[u].size());++i){
        int v=g[u][i];
        if(v==fa)continue;
        dfs(v,u);
        dp[u][0]=min(dp[u][0],dp[v][0]+1);
        dp[u][1]=min(dp[u][1],dp[v][1]+1);
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef mysakure
    freopen("in1.txt","r",stdin);
#endif
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;++i)cin>>v[i];
        for(int i=1;i<=n;++i)g[i].clear();
        for(int i=1;i<n;++i){
            int a,b;
            cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        for(int i=1;i<=n;++i){
            dp[i][1]=dp[i][0]=inf;
        }
        ans=inf;
        dfs(1,-1);
        cout<<ans<<endl;
    }



    return 0;
}