Submission #1693675

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
vector<int> G[N];
int num[N];

int can(int pos,int par){
  int sum = 0;
  for(int to:G[pos]) if(to!=par) sum += num[to];
  if(sum < num[pos]) return 0;
  if(sum == num[pos]) return 1;

  int target = num[pos];
  int a = 0;
  for(int to:G[pos]){
    if(to == par) continue;
    int b = min(abs(sum - target), min(a,num[to]) );
    target -= b;
    sum -= b * 2;
    a = abs(a - num[to]);
    assert(sum>=0 && target >=0);
    if(sum == target){
      num[pos] = target;
      return 1;
    }
  }
  return 0;
}

int check(int pos,int par){
  int res = 1;  
  for(int to:G[pos]){
    if(to == par) continue;
    res &= check(to,pos);
  }
  res &= can(pos,par);
  return res;
}

signed main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++) cin>>num[i];
  
  for(int i=0,a,b;i<n-1;i++){
    cin>>a>>b;  a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int ans = check(0,-1);
  cout<<(ans? "YES":"NO")<<endl;
  return 0;
}

Submission Info

Judge Result