Submission #1460267

---

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;
	long long mach = 0;
	for(long long i = 0; i < tree[cur].size(); i++){
		if(pa == tree[cur][i]){
			continue;
		}
		long long tmp = dfs(cur, tree[cur][i]);
		mach = max(mach, tmp);
		if(tmp < 0){
			return -1;
		}
		child += tmp;
	}

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

	if(down > min(mach, child/2)){
		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