#ifdef DEBUG #define _GLIBCXX_DEBUG #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #endif #include using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n" #define RETURN( ANSWER ) COUT( ANSWER ); QUIT // Resetはm_foundとm_prevも初期化 // Shiftはm_foundとm_prevは非初期化 #define DECLARATION_OF_FIRST_SEARCH( BREADTH ) \ template E(const int&)> \ class BREADTH ## FirstSearch \ { \ \ private: \ int m_V; \ int m_init; \ list m_next; \ bool m_found[V_max]; \ int m_prev[V_max]; \ \ public: \ inline BREADTH ## FirstSearch( const int& V ); \ inline BREADTH ## FirstSearch( const int& V , const int& init ); \ \ inline void Reset( const int& init ); \ inline void Shift( const int& init ); \ \ bool& found( const int& i ); \ const int& prev( const int& i ) const; \ \ int Next(); \ \ }; \ #define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \ template E(const int&)> inline BREADTH ## FirstSearch::BREADTH ## FirstSearch( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \ template E(const int&)> inline BREADTH ## FirstSearch::BREADTH ## FirstSearch( const int& V , const int& init ) : BREADTH ## FirstSearch( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \ \ template E(const int&)> inline void BREADTH ## FirstSearch::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \ template E(const int&)> inline void BREADTH ## FirstSearch::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \ \ template E(const int&)> inline bool& BREADTH ## FirstSearch::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \ template E(const int&)> inline const int& BREADTH ## FirstSearch::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \ \ template E(const int&)> \ int BREADTH ## FirstSearch::Next() \ { \ \ if( m_next.empty() ){ \ \ return -1; \ \ } \ \ const int i_curr = m_next.front(); \ m_next.pop_front(); \ list edge = E( i_curr ); \ \ for( auto itr = edge.begin() , end = edge.end() ; itr != end ; itr++ ){ \ \ const int& i = *itr; \ bool& found_i = found( i ); \ \ if( ! found_i ){ \ \ m_next.PUSH( i ); \ m_prev[i] = i_curr; \ found_i = true; \ \ } \ \ } \ \ return i_curr; \ \ } \ DECLARATION_OF_FIRST_SEARCH( Depth ); DEFINITION_OF_FIRST_SEARCH( Depth , push_front ); inline CEXPR( int , bound_N , 200000 ); list edge[bound_N] = {}; inline list E( const int& i ) { return edge[i]; } int main() { UNTIE; CIN_ASSERT( N , 2 , bound_N ); FOR( i , 1 , N ){ CIN_ASSERT( a , 1 , N ); CIN_ASSERT( b , a + 1 , N ); a--; b--; edge[a].push_back( b ); edge[b].push_back( a ); } bool black[bound_N]; FOR( i , 0 , N ){ CIN_ASSERT( Ci , 0 , 1 ); black[i] = Ci == 1; } DepthFirstSearch dfs{ N , 0 }; list node{}; REPEAT( N ){ node.push_front( dfs.Next() ); } int answer = 0; FOR_ITR( node , itr , end ){ int& i = *itr; if( ! black[i] ){ answer++; if( i != 0 ){ bool& black_i_prev = black[ dfs.prev( i ) ]; black_i_prev = !black_i_prev; } } } RETURN( black[0] ? answer : -1 ); }