Submission #1093059

---

Source Code Expand

// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
#define N 101010
void build(){

}
LL n , a[ N ];
vector<int> v[ N ];
void init(){
  n = getint();
  for( int i = 1 ; i <= n ; i ++ )
    a[ i ] = getint();
  for( int i = 1 ; i < n ; i ++ ){
    int ai = getint();
    int bi = getint();
    v[ ai ].push_back( bi );
    v[ bi ].push_back( ai );
  }
}
LL go( int now , int prt ){
  bool leaf = true;
  LL ret = 0 , mx = 0 , res = 0;
  for( int son : v[ now ] ){
    if( son == prt ) continue;
    leaf = false;
    LL tmp = go( son , now );
    if( tmp < 0 ){
      puts( "NO" );
      Bye;
    }
    LL mr = min( ret , tmp );
    mr = min( mr , ( res + tmp ) / 2 );
    ret += tmp;
    mx += mr;
    res = res + tmp - mr - mr;
  }
  if( leaf ) return a[ now ];
  if( ret < a[ now ] || ret - a[ now ] > mx ){
    puts( "NO" );
    Bye;
  }
  return ret - 2 * ( ret - a[ now ] );
}
void solve(){
  int rt = -1;
  for( int i = 1 ; i <= n ; i ++ )
    if( v[ i ].size() > 1u ){
      rt = i;
      break;
    }
  if( rt == -1 ){
    puts( a[ 1 ] == a[ 2 ] ? "YES" : "NO" );
    Bye;
  }
  if( go( rt , rt ) == 0 )
    puts( "YES" );
  else
    puts( "NO" );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}

Submission Info

Judge Result