首先有一个基本的简化，因为是删一个连通块，所以一个极大的连通块一定会被一起删，所以可以缩成一个点。
然后接下来就是一些手法了，弱化问题，只考虑黑白点，那么经过刚才的操作，树上的同色点一定不相邻，那么很自然的就能想到操作数和直径相关，加上灰点后，实际等价于染白或黑，那么 \texttt{dp} 即可。
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long;
int T;
int n;
const int N=2e5+10,inf=0x3f3f3f;
int a[N];
vector<int>g[N];
void addedge(int u,int v){
g[u].push_back(v);
g[v].push_back(u);
}
int f[N][2],h[N][2];
void pre(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
f[i][0]=f[i][1]=1;
h[i][0]=h[i][1]=1;
a[i]=(a[i]+2)%3;
g[i].clear();
if(a[i]==2)continue;
f[i][a[i]^1]=inf;
h[i][a[i]^1]=inf;
}
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
}
}
void dfs(int u,int fa){
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
}
for(int i=0;i<=1;++i){
int mx=0,mx2=0;
for(int v:g[u]){
if(v==fa)continue;
f[u][i]=max(f[u][i],min(f[v][0],f[v][1]));
if(min(h[v][i],h[v][i^1]+1)>mx){
mx2=mx;
mx=min(h[v][i],h[v][i^1]+1);
}
else if(min(h[v][i],h[v][i^1]+1)>mx2)
mx2=min(h[v][i],h[v][i^1]+1);
}
h[u][i]=max(h[u][i],mx);
f[u][i]=max(f[u][i],mx+mx2-(mx&&mx2));
}
}
void work(){
dfs(1,0);
printf("%d\n",min(f[1][0],f[1][1])/2+1);
}
int main(){
scanf("%d",&T);
while(T--){
pre();
work();
}
return 0;
}