#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int p = 998244353;
int mul(int a, int b) { return (1LL * a * b) % p; }
int add(int a, int b) {
  int s = (a + b);
  if (s >= p) s -= p;
  return s;
}
int sub(int a, int b) {
  int s = (a + p - b);
  if (s >= p) s -= p;
  return s;
}
int po(int a, int deg) {
  if (deg == 0) return 1;
  if (deg % 2 == 1) return mul(a, po(a, deg - 1));
  int t = po(a, deg / 2);
  return mul(t, t);
}
int inv(int n) { return po(n, p - 2); }
mt19937 rnd(time(0));
int n;
vector<int> a;
vector<vector<int>> G;
vector<int> white, black;
bool good = true;
const int MAX = 500000;
int bound;
void dfs(int v, int par = -1) {
  for (auto it : G[v])
    if (it != par) dfs(it, v);
  white[v] = MAX;
  black[v] = MAX;
  if (a[v] != 1) {
    vector<int> guys;
    for (auto it : G[v])
      if (it != par) guys.push_back(min(black[it], white[it] + 1));
    sort(guys.begin(), guys.end());
    if (guys.size() == 0)
      black[v] = 0;
    else if (guys.size() == 1) {
      black[v] = guys[0];
    } else {
      if (guys[guys.size() - 1] + guys[guys.size() - 2] <= bound)
        black[v] = guys[guys.size() - 1];
    }
  }
  if (a[v] != 2) {
    vector<int> guys;
    for (auto it : G[v])
      if (it != par) guys.push_back(min(white[it], black[it] + 1));
    sort(guys.begin(), guys.end());
    if (guys.size() == 0)
      white[v] = 0;
    else if (guys.size() == 1) {
      white[v] = guys[0];
    } else {
      if (guys[guys.size() - 1] + guys[guys.size() - 2] <= bound)
        white[v] = guys[guys.size() - 1];
    }
  }
  if (black[v] > bound && white[v] > bound) good = false;
}
bool check(int t) {
  bound = t;
  white.clear();
  black.clear();
  white.resize(n);
  black.resize(n);
  good = true;
  dfs(n - 1);
  return good;
}
void solve() {
  a.clear();
  G.clear();
  cin >> n;
  a.resize(n);
  G.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  int L = 0;
  int R = 300000;
  if (check(L)) {
    cout << 1 << '\n';
    return;
  }
  while (R - L > 1) {
    int mid = (L + R) / 2;
    if (check(mid))
      R = mid;
    else
      L = mid;
  }
  cout << (R + 3) / 2 << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) solve();
}
