#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); // compute dp[v][parentPress][pressV] // follow editorial: tmp[pressV][parity] for (int parentPress = 0; parentPress <= 1; ++parentPress) { for (int pressV = 0; pressV <= 1; ++pressV) { // actually will compute after merging children // but we will compute tmp independent of parentPress, using pressV in indexing as in editorial. } } // For each possible pressV (this is the "v pressed or not" value used when merging child's parentPress) // We compute tmp[0/1][0/1] as editorial describes, but need values for both parentPress later. // Implementation: for each parentPress i and pressV j we need tmp[*][j], where tmp indices first dim 0/1 correspond to whether v is pressed in the tmp's meaning. // The editorial uses tmp[0][0], tmp[0][1], tmp[1][0], tmp[1][1] where first index = whether v pressed, second = parity. // Build tmp for both pressV = 0 and pressV = 1 simultaneously by running loop for pressV. for (int pv = 0; pv <= 1; ++pv) { 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 ntmp[2][2]; ntmp[0][0] = ntmp[0][1] = ntmp[1][0] = ntmp[1][1] = INF; // apply editorial merge formulas (child's parentPress values are 0 or 1) // Note: dp[to][a][b] means for child 'to', parentPress = a, pressChild = b. // When computing tmp[0][0] (v not pressed, even), editorial uses dp[0][1][to] and dp[0][0][to], etc. // Implement directly: // tmp[0][0] = min(tmp[1][0] + dp[0][1][to], tmp[0][0] + dp[0][0][to]) ntmp[0][0] = min( tmp[1][0] >= INF || dp[to][0][1] >= INF ? INF : tmp[1][0] + dp[to][0][1], tmp[0][0] >= INF || dp[to][0][0] >= INF ? INF : tmp[0][0] + dp[to][0][0] ); // tmp[0][1] = min(tmp[1][1] + dp[1][1][to], tmp[0][1] + dp[1][0][to]) ntmp[0][1] = min( tmp[1][1] >= INF || dp[to][1][1] >= INF ? INF : tmp[1][1] + dp[to][1][1], tmp[0][1] >= INF || dp[to][1][0] >= INF ? INF : tmp[0][1] + dp[to][1][0] ); // tmp[1][0] = min(tmp[0][0] + dp[0][1][to], tmp[1][0] + dp[0][0][to]) ntmp[1][0] = min( tmp[0][0] >= INF || dp[to][0][1] >= INF ? INF : tmp[0][0] + dp[to][0][1], tmp[1][0] >= INF || dp[to][0][0] >= INF ? INF : tmp[1][0] + dp[to][0][0] ); // tmp[1][1] = min(tmp[0][1] + dp[1][1][to], tmp[1][1] + dp[1][0][to]) ntmp[1][1] = min( tmp[0][1] >= INF || dp[to][1][1] >= INF ? INF : tmp[0][1] + dp[to][1][1], tmp[1][1] >= INF || dp[to][1][0] >= INF ? INF : tmp[1][1] + dp[to][1][0] ); tmp[0][0] = min(tmp[0][0], ntmp[0][0]); // keep best (defensive) tmp[0][1] = min(tmp[0][1], ntmp[0][1]); tmp[1][0] = min(tmp[1][0], ntmp[1][0]); tmp[1][1] = min(tmp[1][1], ntmp[1][1]); // Actually assign to ntmp to continue correctly tmp[0][0] = ntmp[0][0]; tmp[0][1] = ntmp[0][1]; tmp[1][0] = ntmp[1][0]; tmp[1][1] = ntmp[1][1]; } // Now tmp corresponds to the case "v pressed = pv" in editorial indexing. // For each possible parentPress i and pressV j we will read tmp[pv][j] or tmp[1][j] depending on need. // Store interim results in a temp array by pv // We'll write these into dp[v] after finishing pv loop for both pv=0,1 // To simplify, store tmp results into a small array // Save into dp_temp_for_pv[pv][parity] // Use a static local container: static ll saved_tmp[2][2][2]; for (int parity = 0; parity <= 1; ++parity) { saved_tmp[pv][0][parity] = tmp[0][parity]; saved_tmp[pv][1][parity] = tmp[1][parity]; } // After finishing pv loops, will use saved_tmp to compute dp[v][*][*]. // BUT note: saved_tmp is static and must carry across iterations; copy out now. // We'll handle assignment outside of this pv loop by storing into dp using saved_tmp references. // To avoid complexity, copy saved_tmp into dp after both pv iterations. if (pv == 1) { // retrieve both pv=0 and pv=1 saved tmp values ll t00 = saved_tmp[0][0][0]; ll t01 = saved_tmp[0][0][1]; ll t10 = saved_tmp[0][1][0]; ll t11 = saved_tmp[0][1][1]; ll s00 = saved_tmp[1][0][0]; ll s01 = saved_tmp[1][0][1]; ll s10 = saved_tmp[1][1][0]; ll s11 = saved_tmp[1][1][1]; // Compute dp[v][parentPress][pressV] for all 4 combinations for (int i = 0; i <= 1; ++i) { for (int j = 0; j <= 1; ++j) { int toggles = (i + j) & 1; int needParity = initState[v] ^ toggles; // 0 -> children even, 1 -> children odd // choose tmp corresponding to pressV = j if (j == 0) { // tmp for pv=0: t** if (needParity == 0) dp[v][i][j] = (ll)j + ( (t00 >= INF) ? INF : t00 ); else dp[v][i][j] = (ll)j + ( (t01 >= INF) ? INF : t01 ); } else { // tmp for pv=1: s** if (needParity == 0) dp[v][i][j] = (ll)j + ( (s10 >= INF) ? INF : s10 ); // careful mapping else dp[v][i][j] = (ll)j + ( (s11 >= INF) ? INF : s11 ); // Note: s10/s11 correspond to saved_tmp[1][1][parity] etc. // However earlier saved_tmp layout: saved_tmp[pv][x][parity] where x indexes ??? // To avoid confusion, recompute properly below using a safe approach. } } } // The above has confusion due to saved_tmp indexing chosen. Instead recompute dp directly using fresh tmp builds per (pressV). } } // Simpler and correct approach: rebuild tmp separately for pressV=0 and pressV=1 and then compute dp. // Do that cleanly here (overwrite dp[v] with correct values). // Recompute tmp for pv=0 { ll tmp0[2] = {0, INF}; // tmp when v not pressed: tmp0[parity] for (int to : g[v]) { if (to == p) continue; ll n0[2] = {INF, INF}; // tmp0_even = min(prev_odd + dp[to][0][1], prev_even + dp[to][0][0]) n0[0] = min( tmp0[1] >= INF || dp[to][0][1] >= INF ? INF : tmp0[1] + dp[to][0][1], tmp0[0] >= INF || dp[to][0][0] >= INF ? INF : tmp0[0] + dp[to][0][0] ); // tmp0_odd = min(prev_odd + dp[to][1][1], prev_even + dp[to][1][0]) -- note editorial's formula used tmp[1][1] + dp[1][1] and tmp[0][1] + dp[1][0] // But correct merging for tmp[0][1] as per editorial: n0[1] = min( tmp0[1] >= INF || dp[to][1][1] >= INF ? INF : tmp0[1] + dp[to][1][1], tmp0[0] >= INF || dp[to][1][0] >= INF ? INF : tmp0[0] + dp[to][1][0] ); tmp0[0] = n0[0]; tmp0[1] = n0[1]; } ll tmp1[2] = {0, INF}; // tmp when v pressed for (int to : g[v]) { if (to == p) continue; ll n1[2] = {INF, INF}; n1[0] = min( tmp1[1] >= INF || dp[to][0][1] >= INF ? INF : tmp1[1] + dp[to][0][1], tmp1[0] >= INF || dp[to][0][0] >= INF ? INF : tmp1[0] + dp[to][0][0] ); n1[1] = min( tmp1[1] >= INF || dp[to][1][1] >= INF ? INF : tmp1[1] + dp[to][1][1], tmp1[0] >= INF || dp[to][1][0] >= INF ? INF : tmp1[0] + dp[to][1][0] ); tmp1[0] = n1[0]; tmp1[1] = n1[1]; } for (int i = 0; i <= 1; ++i) { for (int j = 0; j <= 1; ++j) { int toggles = (i + j) & 1; int needParity = initState[v] ^ toggles; if (j == 0) { if (needParity == 0) dp[v][i][j] = (ll)j + tmp0[0]; else dp[v][i][j] = (ll)j + tmp0[1]; } else { if (needParity == 0) dp[v][i][j] = (ll)j + tmp1[0]; else dp[v][i][j] = (ll)j + tmp1[1]; } if (dp[v][i][j] > INF) dp[v][i][j] = INF; } } } } void Bai() { // choose root = 1 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; }