Submission #1693612

---

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 ans = 1;
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(target-sum),min(a,num[to]));
    target -= b;
    sum -= b * 2;

    if(sum == target){
      num[pos] = sum;
      return 1;
    }
    a = abs(a - num[to]);
  }
  return 0;
}

int check(int pos,int par){
  if(G[pos].size() == 1) return 1;

  int sum = 0;
  for(int to:G[pos]){
    if(to == par) continue;
    sum += num[to];
    if(check(to,pos) == 0) return ans = 0;
  }
  return ans = can(pos,par);
}


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);
  }

  for(int to:G[0]) check(to,0);
  cout<<(ans? "YES":"NO")<<endl;
  return 0;
}

Submission Info

Judge Result