#include "bits/stdc++.h" using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back bool is_digit(char c) { return c >= '0'; } int fastin(){ int x = 0; int s = 1; char c; c = getchar_unlocked(); if (c == '-') s = -1; else x = c - '0'; while (is_digit(c = getchar())) { x = x * 10 + c - '0'; } return s*x; } void write_int(unsigned long x) { char t[19]; int i = 0; do { int d = x%10; t[i++] = '0'+d; x /= 10; } while (x > 0) ; while (--i >= 0) { putchar_unlocked(t[i]); } putchar_unlocked('\n'); } const int inf = 1e9; struct node { int dp[2][2]; node() { dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = inf; } node(int x) { dp[1-x][0] = dp[1-x][1] = 1; dp[x][1] = 0; dp[x][0] = inf; } }; node comb(const node &a, const node &b) { node res; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { for (int x = 0; x < 2; ++x) { for (int y = 0; y < 2; ++y) { if (j && y) continue; int col = i, add = 0; if (!x) { col ^= 1; add += 2; } if (y) { res.dp[col][1] = min(res.dp[col][1], a.dp[i][j] + b.dp[x][y] + add); } else { if (!j) res.dp[col][1] = min(res.dp[col][1], a.dp[i][j] + b.dp[x][y] + add); add++; col ^= 1; res.dp[col][j] = min(res.dp[col][j], a.dp[i][j] + b.dp[x][y] + add); } } } } } return res; } const int N = 500'000; node dp[2*N], dp_v[N]; vector<int> g[N], rev[N]; bool skip[2*N]; int st[2*N], u[2*N], v[2*N]; //vector<node> edge_dp(const vector<int> &u, const vector<int> &v, // const vector<vector<int>> &g, const vector<int> &c) { void edge_dp(const vector<int> &c) { int n = ssize(c); int m = 2 * (n-1); // vector<bool> skip(m); // vector<node> dp(m); for (int i = 0; i < m; ++i) if (c[v[i]]) skip[i] = true; for (int i = 0; i < m; ++i) dp[i] = node(c[v[i]]); // vector<vector<int>> rev(n); for (int i = 0; i < m; ++i) rev[v[i]].eb(i); stack<int> s; // vector<int> st(m); for (int i = 0; i < m; ++i) { st[i] = ssize(g[v[i]]) - 1; if (!st[i]) s.push(i); } while (ssize(s)) { int e = s.top(); s.pop(); for (int idx : g[v[e]]) { if (idx == (e^1)) continue; if (!skip[idx]) { dp[e] = comb(dp[e], dp[idx]); skip[e] = false; } } for (int idx : rev[u[e]]) { if (idx == (e^1)) continue; if (--st[idx] == 0) s.push(idx); } } // vector<node> dp_v(n); for (int i = 0; i < n; ++i) dp_v[i] = node(c[i]); for (int i = 0; i < n; ++i) { for (int idx : g[i]) { if (!skip[idx]) { dp_v[i] = comb(dp_v[i], dp[idx]); } } } // return dp_v; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n = fastin(); vector<int> c(n); // vector<vector<int>> g(n); debug(n); for (int i = 0; i < n; ++i) { char x; // cin >> x; x = getchar_unlocked(); c[i] = int(x - '0'); debug(x); } getchar_unlocked(); // vector<int> u(2*n-2), v(2*n-2); for (int i = 0; i < n-1; ++i) { int a = fastin(), b = fastin(); --a; -- b; u[2*i] = v[2*i+1] = a; v[2*i] = u[2*i+1] = b; g[u[2*i]].eb(2*i); g[u[2*i+1]].eb(2*i+1); } edge_dp(c); int res = inf; for (int i = 0; i < n; ++i) res = min(res, min(dp_v[i].dp[1][0], dp_v[i].dp[1][1])); // cout << res << '\n'; write_int(res); return 0; }