Submission #1095942

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;

#define fi first
#define se second
typedef long long LL;
typedef long double LD;

LL N,a[100010],v[100010];
vector<int> g[100010];

bool dfs(int nod, int f){
    int i;  LL sum=0,d;

    if (g[nod].size()==1){
        v[nod]=a[nod];
        return 1;
    }

    for (i=0; i<(int)g[nod].size(); i++)
        if (g[nod][i]!=f){
            if (!dfs(g[nod][i],nod)) return 0;
            sum+=v[g[nod][i]];
        }

    d=2*a[nod]-sum;
    if (d<0) return 0;
    v[nod]=d;

    sum=0; int nxt;
    for (i=0; i<(int)g[nod].size(); i++){
        nxt=g[nod][i];
        if (nxt==f) continue;
        sum=min(2*(a[nod]-d),sum+min(a[nod]-d,v[nxt]));
    }

    if (sum<2*(a[nod]-d)) return 0;
    return 1;
}

int main(){
    cin >> N;

    int i;
    for (i=1; i<=N; i++) cin >> a[i];

    int x,y;
    for (i=1; i<N; i++){
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    if (N==2){
        if (a[1]==a[2]) cout << "YES\n";
        else cout << "NO\n";
        return 0;
    }

    for (i=1; i<=N; i++)
        if (g[i].size()>1){
            bool p=dfs(i,0);
            if (!p || v[i]!=0) cout << "NO\n";
            else cout << "YES\n";
            return 0;
        }

    return 0;
}

Submission Info

Judge Result