#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 const int inf = 1e9; struct node { int dp[2][2]; bool skip; node() { dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = inf; skip = false; } node(int x) { dp[1-x][0] = dp[1-x][1] = 1; dp[x][1] = 0; dp[x][0] = inf; skip = bool(x); } }; node comb(const node &a, const node &b) { node res; res.skip = a.skip && b.skip; if (res.skip) return 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; } node calc_dp(int v, int p, const vector<vector<int>> &g, const vector<node> &dp, const vector<int> &c) { node res(c[v]); for (int u : g[v]) { if (u == p) continue; if (!dp[u].skip) res = comb(res, dp[u]); } return res; } void dfs(int v, int p, const vector<vector<int>> &g, vector<node> &dp, const vector<int> &c) { for (int u : g[v]) { if (u == p) continue; dfs(u, v, g, dp, c); } dp[v] = calc_dp(v, p, g, dp, c); } vector<node> solve_dp(int s, const vector<vector<int>> &g, const vector<int> &c) { int n = ssize(g); vector<node> dp(n); dfs(s, -1, g, dp, c); return dp; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> c(n); vector<vector<int>> g(n); for (int i = 0; i < n; ++i) { char x; cin >> x; c[i] = int(x - '0'); } debug(c); for (int i = 0; i < n-1; ++i) { int u, v; cin >> u >> v; g[u-1].eb(v-1); g[v-1].eb(u-1); } int res = inf; for (int i = 0; i < n; ++i) { vector<node> dp = solve_dp(i, g, c); // reroot dfs(0, -1, g, dp, c); res = min(res, min(dp[i].dp[1][0], dp[i].dp[1][1])); } cout << res << '\n'; return 0; }