#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N][4],n,a[N];
#define pb push_back
vector<int>g[N];
int ans;
void ad(int &x,int y){if(x>y)x=y;}
void dfs(int x,int f){
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)dp[x][i|(j<<1)]=(i?a[x]:0)+(j?-a[x]:0)+1;
    for(int v:g[x])if(v!=f){
        dfs(v,x);
        for(int i=0;i<4;i++)ans=min(ans,dp[x][i]+dp[v][3^i]);
        for(int i=1;i>=0;i--)for(int j=1;j>=0;j--)for(int i_=1;i_>=0;i_--)
        for(int j_=1;j_>=0;j_--){
            if(i&&i_)continue;if(j&&j_)continue;
            ad(dp[x][i|i_|((j|j_)<<1)],dp[v][i|(j<<1)]+(i_?a[x]:0)+(j_?-a[x]:0)+1);
        }
    }
}
void sol(){
    ans=1;
    scanf("%d",&n);for(int i=1;i<=n;i++)g[i].clear();
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v),g[v].pb(u);
    }
    dfs(1,0);printf("%d\n",ans);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}