#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 5e5 + 7;
vector<int> graf[MAXN];
int dp[MAXN][2][2]; //zmiana parent, koncze w v
bool color[MAXN];
int xorr[MAXN];
int optsuma[MAXN];
multiset<pair<int, int>> opt1[MAXN];
multiset<pair<int, int>> opt2[MAXN];
void policz(int v) {
dp[v][0][0] = 1e9;
dp[v][0][1] = 1e9;
dp[v][1][0] = 1e9;
dp[v][1][1] = 1e9;
// czesc kosztowna
if (opt1[v].size()) {
int koszt = (*(opt1[v].begin())).first;
int koszt2 = (*(opt1[v].begin())).second;
dp[v][0][0] = min(dp[v][0][0], optsuma[v] + koszt + (xorr[v] ^ 1) * (int)1e7 - 1);
dp[v][0][0] = min(dp[v][0][0], optsuma[v] + koszt2 + (xorr[v] ) * (int)1e7 - 1);
dp[v][1][0] = min(dp[v][1][0], optsuma[v] + koszt + (xorr[v]) * (int)1e7 - 1 + 2);
dp[v][1][0] = min(dp[v][1][0], optsuma[v] + koszt2 + (xorr[v] ^ 1) * (int)1e7 - 1 + 2);
}
if (opt2[v].size()) {
int koszt = (*(opt2[v].begin())).first;
int koszt2 = (*(opt2[v].begin())).second;
dp[v][0][0] = min(dp[v][0][0], optsuma[v] + koszt + (xorr[v]) * (int)1e7 - 1);
dp[v][0][0] = min(dp[v][0][0], optsuma[v] + koszt2 + (xorr[v] ^ 1) * (int)1e7 - 1);
dp[v][1][0] = min(dp[v][1][0], optsuma[v] + koszt + (xorr[v] ^ 1) * (int)1e7 - 1 + 2);
dp[v][1][0] = min(dp[v][1][0], optsuma[v] + koszt2 + (xorr[v]) * (int)1e7 - 1 + 2);
}
// for (int s : graf[v]) {
// if (s == p) continue;
// int oh = dp[s][0][1] > dp[s][1][1];
// int optsuma2 = optsuma - min(dp[s][0][1], dp[s][1][1]);
// //cout << "O: " << v << ' ' << s << ' ' << min(dp[s][0][1], dp[s][1][1]) << ' ' << optsuma << ' ' << optsuma2 << ' ' << dp[s][0][0] << ' ' << xorr << ' ' << oh << '\n';
// dp[v][0][0] = min(dp[v][0][0], optsuma2 + dp[s][0][0] + (xorr ^ oh) * (int)1e7 - 1);
// dp[v][0][0] = min(dp[v][0][0], optsuma2 + dp[s][1][0] + (xorr ^ oh ^ 1) * (int)1e7 - 1);
// dp[v][1][0] = min(dp[v][1][0], optsuma2 + dp[s][0][0] + (xorr ^ oh ^ 1) * (int)1e7 - 1 + 2);
// dp[v][1][0] = min(dp[v][1][0], optsuma2 + dp[s][1][0] + (xorr ^ oh) * (int)1e7 - 1 + 2);
// }
// koniec czesci kosztownej
if (!xorr[v]) dp[v][1][1] = optsuma[v] + 2;
else dp[v][0][1] = optsuma[v];
dp[v][0][0] = min(dp[v][0][0], dp[v][0][1]);
dp[v][1][0] = min(dp[v][1][0], dp[v][1][1]);
}
void change(int v, int v2) {
xorr[v] ^= 1; //juz nie root
optsuma[v] --; //juz nie root
xorr[v2] ^= 1; // tera root
optsuma[v2] ++; //tera root
//pierwsze roota, potem nowy
if (dp[v2][0][1] > dp[v2][1][1]) {
opt1[v].extract({dp[v2][0][0] - dp[v2][1][1], dp[v2][1][0] - dp[v2][1][1]});
xorr[v] ^= 1;
}
else {
opt2[v].extract({dp[v2][0][0] - dp[v2][0][1], dp[v2][1][0] - dp[v2][0][1]});
}
optsuma[v] -= min(dp[v2][0][1], dp[v2][1][1]);
if (graf[v].size() == 1) {
dp[v][0][0] = 1;
dp[v][0][1] = 1;
dp[v][1][1] = 5;
dp[v][1][0] = 5;
}
else policz(v);
if (dp[v][0][1] > dp[v][1][1]) {
opt1[v2].insert({dp[v][0][0] - dp[v][1][1], dp[v][1][0] - dp[v][1][1]});
xorr[v2] ^= 1;
}
else {
opt2[v2].insert({dp[v][0][0] - dp[v][0][1], dp[v][1][0] - dp[v][0][1]});
}
optsuma[v2] += min(dp[v][0][1], dp[v][1][1]);
policz(v2);
} //do napisania
void dfs(int v, int p) {
opt1[v].clear();
opt2[v].clear();
xorr[v] = (graf[v].size()) % 2;
optsuma[v] = graf[v].size() + (v == p);
if (v == p) xorr[v] ^= 1;
xorr[v] ^= color[v];
if (v != p && graf[v].size() == 1) {
dp[v][0][0] = 1;
dp[v][0][1] = 1;
dp[v][1][1] = 5;
dp[v][1][0] = 5;
return;
}
for (int s : graf[v]) {
if (s != p) {
dfs(s, v);
if (dp[s][0][1] > dp[s][1][1]) {
xorr[v] ^= 1;
opt1[v].insert({dp[s][0][0] - dp[s][1][1], dp[s][1][0] - dp[s][1][1]});
}
else {
opt2[v].insert({dp[s][0][0] - dp[s][0][1], dp[s][1][0] - dp[s][0][1]});
}
optsuma[v] += min(dp[s][0][1], dp[s][1][1]);
}
}
policz(v);
// cout << v << ": " << dp[v][0][0] << ' ' << dp[v][0][1] << ' ' << dp[v][1][0] << ' ' << dp[v][1][1] << ' ' << optsuma << ' ' << xorr << '\n';
}
int ans = 1e9;
void dfs2(int v, int p) {
ans = min({ans, dp[v][0][0], dp[v][0][1], dp[v][1][1]});
for (int s : graf[v]) {
if (s != p) {
change(v, s);
dfs2(s, v);
change(s, v);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, a, b;
cin >> n;
vector<bool> blocked(n + 1, 0);
vector<int> indegree(n + 1, 0);
char c;
for (int i = 1; i <= n; i++) {
cin >> c;
color[i] = c - '0';
}
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
indegree[a]++;
indegree[b]++;
}
vector<int> kolejka;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 1 && color[i]) kolejka.push_back(i);
}
while (kolejka.size()) {
int v = kolejka.back();
blocked[v] = 1;
kolejka.pop_back();
for (int s : graf[v]) {
indegree[s] --;
if (indegree[s] == 1 && color[s]) kolejka.push_back(s);
}
}
for (int i = 1; i <= n; i++) {
if (blocked[i]) {
graf[i].clear();
continue;
}
vector<int> s2;
for (int s : graf[i]) {
if (!blocked[s]) s2.push_back(s);
}
graf[i] = s2;
}
for (int i = 1; i <= n; i++) {
if (!blocked[i]) {
dfs(i, i);
dfs2(i, i);
break;
}
}
// for (int i = 1; i <= n; i++) {
// if (blocked[i]) continue;
// dfs(i, i);
// //cout << dp[i][0][0] << ' ' << dp[i][0][1] << ' ' << dp[i][1][1] << '\n';
// ans = min({ans, dp[i][0][0], dp[i][0][1], dp[i][1][1]});
// }
cout << ans << '\n';
return 0;
}
