#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; vi dep[2], d; void dfs(int pos, int prev = -1) { dep[d[pos]%2].push_back(pos); for(int adj: adjL[pos]) { if(adj == prev) continue; d[adj] = d[pos] + 1; dfs(adj, pos); } } 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); } d.assign(n, 0); dfs(0, 0); int chosen = 0, ans = n+1; if((int)dep[1].size() < n/2) chosen = 1; int siz = dep[chosen].size(); vi state(n); for(int i=0; i<n; ++i) cin >> state[i]; for(int mask=0; mask<(1<<siz); ++mask) { int cnt = __builtin_popcount(mask); vi tmp(state.begin(), state.end()); for(int j=0; j<siz; ++j) { if((1<<j)&mask) { tmp[dep[chosen][j]] = 1-tmp[dep[chosen][j]]; for(int adj: adjL[dep[chosen][j]]) tmp[adj] = 1-tmp[adj]; } } for(int x=0; x<n; ++x) { if(tmp[x] && d[x]%2 != chosen) { ++cnt; tmp[x] = 1-tmp[x]; for(int adj: adjL[x]) tmp[adj] = 1-tmp[adj]; } } bool valid = 1; for(int x: tmp) if(x) { valid = 0; break; } if(valid) 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(); } }