#include <bits/stdc++.h>
#define int long long
#define endll '\n';
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int mod = 1e9 + 7, N = 1e6;
int n;
vector<int> g[N + 3];

int mx1, mx2;
int ar[N + 3], vis[N + 3];
int dis[N + 3];
int lastNode;
int tracked[N + 3];
int par[N + 3];
int cost[N + 3];
int node2 = 0;
int mx = -1;
int node1 = 0;
void dfs1(int u)
{
  vis[u] = 1;

  if (dis[u] > mx && ar[u])
  {
    mx = dis[u];
    node1 = u;
  }

  for (auto v : g[u])
  {
    if (vis[v] == 0)
    {
      dis[v] = dis[u] + 1;

      dfs1(v);
    }
  }
}

void dfs2(int u)
{
  vis[u] = 1;

  if (dis[u] > mx && ar[u])
  {
    mx = dis[u];
    node2 = u;
  }

  for (auto v : g[u])
  {
    if (vis[v] == 0)
    {
      par[v] = u;
      dis[v] = dis[u] + 1;
      dfs2(v);
    }
  }
}
void dfs3(int u)
{
  vis[u] = 1;

  for (auto v : g[u])
  {
    if (vis[v] == 0)
    {

      dfs3(v);
    }
  }
  // cout << cost[u] <<
  if (cost[u])
  {
    cost[par[u]] += (cost[u] + 2);
  }
  else
  {
    if (ar[u])
    {
      cost[par[u]] += 2;
    }
  }

  // cout << u << "__ " << cost[par[u]] << endll;
}

void solve()
{
  cin >> n;
  mx = -1;
  node1 = 0;
  node2 = 0;
  for (int i = 1; i <= n; i++)
  {
    g[i].clear();
    vis[i] = par[i] = cost[i] = ar[i] = dis[i] = lastNode = tracked[i] = 0;
    mx1 = -1,
    mx2 = 0;
  }
  int c = 0;
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
    if (ar[i])
      c++;
  }

  for (int i = 1; i < n; i++)
  {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  if (c <= 1)
  {
    cout << 0 << endl;
    return;
  }

  // node1
  dfs1(1);
  for (int i = 1; i <= n; i++)
    vis[i] = 0, dis[i] = 0;
  mx = -1;
  // node2
  dfs2(node1);
  int ans = -dis[node2];
  for (int i = 1; i <= n; i++)
    vis[i] = 0, dis[i] = 0;
  mx = -1;

  dfs3(node1);
  // cout << ans << " " << cost[node1] << endl;
  cout << ans + cost[node1] << endll;
}

int32_t main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--)
  {
    solve();
  }
  return 0;
}