Submission #1460298

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

long long N;
long long A[100005];
vector<long long> tree[100005];

//上に流れる分
long long dfs(long long pa, long long cur){

	//leaf
	if(tree[cur].size() == 1 && tree[cur][0] == pa){
		return A[cur];
	}

	long long child = 0;
	vector<long long>chs;
	for(long long i = 0; i < tree[cur].size(); i++){
		if(pa == tree[cur][i]){
			continue;
		}
		long long tmp = dfs(cur, tree[cur][i]);
		chs.push_back(tmp);
		if(tmp < 0){
			return -1;
		}
		child += tmp;
	}

	long long up = (2 * A[cur] - child);
	long long down = (child - A[cur]);
	if(up < 0 || down < 0){
		return -1;
	}

	sort(chs.begin(), chs.end());
	long long num = 0;
	for(long long i = 0; i < chs.size(); i++){
		num += min(chs[i], down);
	}
	if(num < 2 * down){
		return -1;
	}
	return up;
}

int main(){
	cin >> N;
	for(long long i = 0; i < N; i++){
		cin >> A[i];
	}
	for(long long i = 0; i < N - 1; i++){
		long long a,b;
		cin >> a >> b;
		a--;b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	long long ret = dfs(-1, 0);
	if(ret < 0){
		cout << "NO" << endl;
		return 0;
	}

	if(tree[0].size() == 1){
		if(A[0] == ret){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	}else{
		if(0 == ret){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	}
}

Submission Info

Judge Result