#include <bits/stdc++.h> using namespace std; void Init() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } typedef long long ll; const int MAXN = 200000 + 5; const ll INF = (ll)4e18; int n; vector<int> g[MAXN]; int initState[MAXN]; // 0 = off, 1 = on ll dp[MAXN][2][2]; // dp[v][parentPress][pressV] int parentArr[MAXN]; void Input() { cin >> n; for (int i = 1; i <= n; ++i) { g[i].clear(); initState[i] = 0; } for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } string token; cin >> token; if ((int)token.size() == n) { for (int i = 1; i <= n; ++i) initState[i] = token[i-1] - '0'; } else { initState[1] = stoi(token); for (int i = 2; i <= n; ++i) cin >> initState[i]; } } void dfs(int v, int p) { parentArr[v] = p; for (int to : g[v]) if (to != p) dfs(to, v); // initialize dp[v] with INF for (int i = 0; i <= 1; ++i) for (int j = 0; j <= 1; ++j) dp[v][i][j] = INF; // tmp[first][second] as in editorial: // first = whether v is pressed (0/1) // second = parity of number of children pressed (0 = even, 1 = odd) ll tmp[2][2]; tmp[0][0] = 0; tmp[0][1] = INF; tmp[1][0] = 0; tmp[1][1] = INF; for (int to : g[v]) { if (to == p) continue; ll newTmp[2][2]; newTmp[0][0] = newTmp[0][1] = newTmp[1][0] = newTmp[1][1] = INF; // apply editorial merge formulas exactly // newTmp[0][0] = min(tmp[1][0] + dp[to][0][1], tmp[0][0] + dp[to][0][0]) if (tmp[1][0] < INF && dp[to][0][1] < INF) newTmp[0][0] = min(newTmp[0][0], tmp[1][0] + dp[to][0][1]); if (tmp[0][0] < INF && dp[to][0][0] < INF) newTmp[0][0] = min(newTmp[0][0], tmp[0][0] + dp[to][0][0]); // newTmp[0][1] = min(tmp[1][1] + dp[to][1][1], tmp[0][1] + dp[to][1][0]) if (tmp[1][1] < INF && dp[to][1][1] < INF) newTmp[0][1] = min(newTmp[0][1], tmp[1][1] + dp[to][1][1]); if (tmp[0][1] < INF && dp[to][1][0] < INF) newTmp[0][1] = min(newTmp[0][1], tmp[0][1] + dp[to][1][0]); // newTmp[1][0] = min(tmp[0][0] + dp[to][0][1], tmp[1][0] + dp[to][0][0]) if (tmp[0][0] < INF && dp[to][0][1] < INF) newTmp[1][0] = min(newTmp[1][0], tmp[0][0] + dp[to][0][1]); if (tmp[1][0] < INF && dp[to][0][0] < INF) newTmp[1][0] = min(newTmp[1][0], tmp[1][0] + dp[to][0][0]); // newTmp[1][1] = min(tmp[0][1] + dp[to][1][1], tmp[1][1] + dp[to][1][0]) if (tmp[0][1] < INF && dp[to][1][1] < INF) newTmp[1][1] = min(newTmp[1][1], tmp[0][1] + dp[to][1][1]); if (tmp[1][1] < INF && dp[to][1][0] < INF) newTmp[1][1] = min(newTmp[1][1], tmp[1][1] + dp[to][1][0]); // move newTmp -> tmp tmp[0][0] = newTmp[0][0]; tmp[0][1] = newTmp[0][1]; tmp[1][0] = newTmp[1][0]; tmp[1][1] = newTmp[1][1]; } // now compute dp[v][i][j] for all i (parentPress) and j (pressV) for (int i = 0; i <= 1; ++i) { for (int j = 0; j <= 1; ++j) { int toggles = (i + j) & 1; // after toggles parentPress+pressV, v's state = initState[v] ^ toggles // if that equals 1 (ON) -> need odd number of children pressed -> use tmp[j][1] // else need even -> use tmp[j][0] if ((initState[v] ^ toggles) == 1) { if (tmp[j][1] < INF) dp[v][i][j] = (ll)j + tmp[j][1]; } else { if (tmp[j][0] < INF) dp[v][i][j] = (ll)j + tmp[j][0]; } if (dp[v][i][j] > INF) dp[v][i][j] = INF; } } } void Bai() { // choose root = 1 (any root works) dfs(1, 0); ll ans = min(dp[1][0][0], dp[1][0][1]); if (ans >= INF/2) cout << -1 << '\n'; else cout << ans << '\n'; } int main() { Init(); Input(); Bai(); return 0; }