#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;
void dfs1(int u)
{
  vis[u] = 1;

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

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

  for (auto v : g[u])
  {
    if (vis[v] == 0)
    {
      dis[v] = dis[u] + 1;
      if (dis[v] >= mx && ar[v])
      {
        node2 = v;
      }
      par[v] = u;
      dfs2(v);
    }
  }
}

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

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

      dfs3(v);
    }
  }

  if (tracked[u] == 0)
  {
    cost[par[u]] += cost[u] * 2 + ar[u] * 2;
  }
  else
  {
    if (cost[u])
    {
      cost[par[u]] += cost[u] + 1;
    }
    cost[par[u]] += ar[u];
  }

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

void solve()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
  }

  for (int i = 1; i < n; i++)
  {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }

  dfs1(1);
  mx = -1;
  mx1 = 1e9;

  mx1 = 1e9, mx2 = -1;
  int node1 = -1;
  for (int i = 1; i <= n; i++)
  {

    vis[i] = 0;
    if (ar[i])
    {
      // cout << "dukse = " << i << endll;
      if (mx1 > dis[i])
      {
        node2 = i;
        mx1 = dis[i];
        node1 = i;
      }
    }

    dis[i] = 0;
  }

  if (node1 == -1)
  {
    cout << 0 << endll;
    return;
  }
  // return;
  // node2 = 0;
  dfs2(node1);
  // return;
  // cout << node1 << " " << node2 << endl;
  // return;
  while (node2 != node1)
  {
    tracked[node2] = 1;
    node2 = par[node2];
  }
  tracked[node1] = 1;
  for (int i = 1; i <= n; i++)
  {
    // cout << i << "_" << tracked[i] << endl;
  }

  for (int i = 1; i <= n; i++)
    vis[i] = 0;

  dfs3(node1);

  cout << cost[node1] << endll;
  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;
  }
}

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