Submission #1372907

---

Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define ld double
#define ull unsigned long long
#define PI pair < int, int > 

const int N = 5e5 + 123;
const int M = 123;
const ld Pi = acos(-1);
const ll Inf = 1e18;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int Sz = 501;
const int MOD = 1e9 + 7;

void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int mult(int a, int b) {
  return 1ll * a * b % mod;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}

int n, a[N];
vector < int > g[N];
multiset < ll > Set[N];

ll dfs(int v, int p = -1) {
  vector < ll > now;
  ll x = a[v];
  ll y = 0;
  for (auto to : g[v]) {
    if (to != p) {
      ll tmp = dfs(to, v);
      y += tmp;
      now.pb(tmp);
    }
  }
  if (now.size() == 0) return x;
  if (x > y) {
    cout << "NO\n";
    exit(0);
  }
  ll z = y - x;
  auto &st = Set[v];
  for (auto i : now) st.insert(i);
  while(z > 0) {
    if (now.size() < 2) break;
    ll mn = *st.begin();
    st.erase(st.find(mn));
    ll mx = *st.rbegin();
    st.erase(st.find(mx));
    ll cur = min(z, mn);
    mn -= cur;
    mx -= cur;
    x -= cur;
    y -= cur;
    z -= cur;
    if (mn > 0) st.insert(mn);
    if (mx > 0) st.insert(mx); 
  }
  if (z > 0) {
    cout << "NO\n";
    exit(0);
  }
  return x;
}
void solve() { 
  scanf("%d", &n);
  for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
  for (int i = 1, u, v;i < n;i++) {
    scanf("%d%d", &u, &v);
    g[u].pb(v);
    g[v].pb(u);
  }
  if (n == 2) {
    if (a[1] != a[2]) cout << "NO\n";
    else cout << "YES\n";
    return;
  }
  int rt = 1;
  while(g[rt].size() == 1) rt++;
  if (dfs(rt) == 0) cout << "YES\n";
  else cout << "NO\n";
}

int main() {
  #ifdef wws
   freopen("in", "r", stdin);
   // freopen("in", "w", stdout);
  #endif 
//  ios_base::sync_with_stdio(0);
  int tt = 1; 
  while(tt--) solve();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:105:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:106:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
                                                ^
./Main.cpp:108:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &u, &v);
                          ^

Judge Result