#include<bits/stdc++.h> using namespace std; using vi = vector<int>; using pi = pair<int,int>; typedef long long ll; #define debug(x) cout << #x << " = " << x << "\n"; #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; const int MOD = 998244353; const int INF = 1e9; template<ll mod> struct modnum { static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); using S = conditional_t<is_big_mod, ll, int>; using L = conditional_t<is_big_mod, __int128, ll>; S x; modnum() : x(0) {} modnum(ll _x) { _x %= static_cast<ll>(mod); if (_x < 0) { _x += mod; } x = _x; } modnum pow(ll n) const { modnum res = 1; modnum cur = *this; while (n > 0) { if (n & 1) res *= cur; cur *= cur; n /= 2; } return res; } modnum inv() const { return (*this).pow(mod-2); } modnum& operator+=(const modnum& a){ x += a.x; if (x >= mod) x -= mod; return *this; } modnum& operator-=(const modnum& a){ if (x < a.x) x += mod; x -= a.x; return *this; } modnum& operator*=(const modnum& a){ x = static_cast<L>(x) * a.x % mod; return *this; } modnum& operator/=(const modnum& a){ return *this *= a.inv(); } friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } }; using mint = modnum<MOD>; template <class T> class SumSegmentTree { private: const T DEFAULT = 0; vector<T> segtree; int len; public: SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {} void set(int ind, T val) { ind += len; segtree[ind] = val; for (; ind > 1; ind /= 2) { segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1]; } } T range_sum(int start, int end) { T sum = DEFAULT; for (start += len, end += len; start < end; start /= 2, end /= 2) { if (start % 2 == 1) { sum += segtree[start++]; } if (end % 2 == 1) { sum += segtree[--end]; } } return sum; } }; struct BIT { vector<ll>b; int n; void init(int _n) { n = _n ; b.assign(n, 0); } inline int lowbit(int x) { return x & (-x); } void update(int x, ll v) { for(int i = x+1 ; i <= n ; i += lowbit(i)) b[i-1] = max(b[i-1], v); } ll query(int x) { ll ans = 0; for(int i = x ; i > 0 ; i -= lowbit(i)) ans = max(ans,b[i-1]); return ans; } } bit; int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1 x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1; } int inv_ecd(int a, int m) { int x, y; int g = gcd(a, m, x, y); if(g != 1) return -1; x = (x + m) % m; return x; } vector<vi>adjL, dp; vi state; // 0 - nije togglean, iskljucen 1 - nije togglean, upaljen 2 - togglean, iskljucen 3 - togglean, upaljen void calc(int pos, int prev) { if(adjL[pos].size() == 2) { int child = adjL[pos][0]; if(child == prev) child = adjL[pos][1]; calc(child, pos); if(state[pos]) { dp[pos][0] = dp[child][2]; dp[pos][1] = dp[child][0]; dp[pos][2] = dp[child][1] + 1; dp[pos][3] = dp[child][3] + 1; } else { dp[pos][1] = dp[child][2]; dp[pos][0] = dp[child][0]; dp[pos][3] = dp[child][1] + 1; dp[pos][2] = dp[child][3] + 1; } return; } else if(adjL[pos].size() == 1) { if(!state[pos]) { dp[pos][0] = 0; dp[pos][3] = 1; } else { dp[pos][1] = 0; dp[pos][2] = 1; } return; } int a = -1, b; for(int adj: adjL[pos]) { if(adj == prev) continue; if(a == -1) a = adj; else b = adj; calc(adj, pos); } if(state[pos]) { dp[pos][0] = min(dp[a][2] + dp[b][0], dp[b][2] + dp[a][0]); dp[pos][1] = min(dp[a][2] + dp[b][2], dp[a][0] + dp[b][0]); dp[pos][2] = min(dp[a][3] + dp[b][3] + 1, dp[a][1] + dp[b][1] + 1); dp[pos][3] = min(dp[a][3] + dp[b][1] + 1, dp[b][3] + dp[a][1] + 1); } else { dp[pos][1] = min(dp[a][2] + dp[b][0], dp[b][2] + dp[a][0]); dp[pos][0] = min(dp[a][0] + dp[b][0], dp[a][2] + dp[b][2]); dp[pos][3] = min(dp[a][3] + dp[b][3] + 1, dp[a][1] + dp[b][1] + 1); dp[pos][2] = min(dp[a][3] + dp[b][1] + 1, dp[b][3] + dp[a][1] + 1); } } void solve() { int n; cin >> n; adjL.assign(n, vi()); for(int i=0; i<n-1; ++i) { int a,b; cin >> a >> b; --a, --b; adjL[a].push_back(b); adjL[b].push_back(a); } dp.assign(n, vi(4, n+1)); state.resize(n); for(int i=0; i<n; ++i) cin >> state[i]; for(int adj: adjL[0]) calc(adj, 0); int ans = n+1, siz = (int)adjL[0].size(); for(int i=0; i<(1<<siz); ++i) { int x = state[0], cnt = 0; if(__builtin_popcount(i)%2) x = 1 - x; if(x) { // moramo ga toggleat ++cnt; for(int j=0; j<siz; ++j) { if(i&(1<<j)) cnt += dp[adjL[0][j]][3]; else cnt += dp[adjL[0][j]][1]; } } else { for(int j=0; j<siz; ++j) { if(i&(1<<j)) cnt += dp[adjL[0][j]][2]; else cnt += dp[adjL[0][j]][0]; } } ans = min(ans, cnt); } if(ans == n+1) cout << "impossible" << endl; else cout << ans << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; while(tc--) { solve(); } }