设 $p_u$ 为 $u$ 子树 $c_u=0$ 的结点与 $c_u=1$ 的结点数量差。

显然在染色方案确定时需要 $p_1=0$，此时答案为 $\max_{i=1}^{n} |p_i|$。（考虑子树内贪心配对，剩下 $|p_u|$ 个结点配对时需要走 $u \to fa_u$ 这条边，这条边的边权为 $p_u$，这里 $fa_u$ 为 $u$ 的父亲）。

最大值最小，考虑二分一个 $m$，要求所有 $|p_u| \le m$，且 $c_1=0$。

设 $f_{x,y}$ 为 $x$ 子树内是否可以使得 $p_u=y$。

强制所有 $y > m$ 的 $f_{x,y}=0$，直接做树上背包即可做到 $O(n^2 \log n)$。

注意到对于一个 $x$，$f_{x,y}=1$ 的结点 $y$ 恰好是一个区间 $[l_x,r_x]$ 内的所有奇数（子树大小是奇数时）或所有偶数（子树大小为偶数时）。

所以树形背包时只需要对于每个结点计算 $p_u$ 的区间 $[l_x,r_x]$ 即可。

时间复杂度被优化到了 $O(n \log n)$。可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=400100;
vector<int> T[N];
int n,l[N],r[N],c[N];
bool dfs(int u,int f,int k){
	l[u]=(c[u]==1?1:-1),r[u]=(c[u]==2?-1:1);
	for(int v:T[u]) if(v!=f){
		if(!dfs(v,u,k)) return 0;
		l[u]+=l[v],r[u]+=r[v];
	}
	int nl=max(l[u],-k),nr=min(r[u],k);
	if((nl-l[u])%2!=0) ++nl; if((nr-r[u])%2!=0) --nr;
	l[u]=nl,r[u]=nr;
	return l[u]>r[u]?0:1;
}
bool check(int mid){
	if(!dfs(1,0,mid)) return 0;
	return l[1]<=0&&r[1]>=0;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=2*n;i++) cin>>c[i];
	for(int i=1,u,v;i<2*n;i++)
		cin>>u>>v,T[u].push_back(v),T[v].push_back(u);
	int L=1,R=n,mid,ans;
	while(L<=R){
		mid=(L+R)>>1;
		if(check(mid)) ans=mid,R=mid-1;
		else L=mid+1;
	}
	return cout<<ans<<'\n',0;
}