#include <iostream> #include <vector> using namespace std; const int MAXN = 1e5; vector<int> graf[MAXN]; vector<int> akt; vector<int> ans; int n; string s; void rek(int val) { if (val == 0) { for (int i = 1; i <= n; i++) { akt.push_back(i); rek(val + 1); akt.pop_back(); } return; } vector<int> ile(n, 0); for (int val : akt) ile[val - 1] ++; bool git = 1; for (int i = 0; i < n; i++) { if (s[i] - '0' == ile[i] % 2) git = 0; } if (git) { if (ans.size() > akt.size() || ans.size() == 0) ans = akt; } if (val == 2 * n || val > (ans.size() == 0 ? 1e9 : ans.size())) return; int v = akt.back(); for (int s : graf[v]) { akt.push_back(s); rek(val + 1); akt.pop_back(); } } int main() { int a, b; cin >> n; cin >> s; for (int i = 0; i < n - 1; i++) { cin >> a >> b; graf[a].push_back(b); graf[b].push_back(a); } rek(0); cout << ans.size() << '\n'; }