#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5;
int a[N], d[N], sum;
vector <int> g[N];
bool Dfs(int v, int p){
bool ok = (a[v] == 1);
for(int u:g[v]){
if(u != p){
d[u] = d[v] + 1;
ok |= Dfs(u, v);
}
}
if(ok == true and v != p) sum += 2;
return ok;
}
void dfs(int v, int p){
for(int u:g[v]){
if(u != p){
d[u] = d[v] + 1;
dfs(u, v);
}
}
}
void sol(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i], d[i] = 0, g[i].clear();
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0, 0);
int node = 0, mx = 0;
for(int i = 0; i < n; i++){
if(a[i]){
if(d[i] >= mx){
mx = d[i];
node = i;
}
}
d[i] = 0;
}
sum = 0;
bool ok = Dfs(node, node);
mx = 0;
for(int i = 0; i < n; i++){
if(a[i]) mx = max(mx, d[i]);
}
cout << sum - mx << endl;
}
signed main(){
int t;
cin >> t;
while(t--){
sol();
}
return 0;
}