Submission #1131144

---

Source Code Expand

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<int> A(N);
	for(int i =0; i < N; i++) cin >> A[i];
	vector< vector<int> > G(N);
	for(int i =0; i < N-1; i++) {
		int a,b;
		cin >> a >> b;
		G[--a].push_back(--b);
		G[b].push_back(a);}
	vector<bool> live(N,true);
	vector<int> L;
	for(int i =0; i < N; i++) if(G[i].size() == 1) L.push_back(i);
	vector<int> S(N,0),D(N);
	vector< vector<int> > Sv(N);
	for(int i =0; i < N; i++) D[i] =G[i].size();
	int n =L.size();
	while(!L.empty()) {
		if(n == N) {
			if((int)L.size() == 2) {
				if(A[L[0]] == A[L[1]]) cout << "YES\n";
				else cout << "NO\n";}
			else {
				if(A[L[0]] == 0) cout << "YES\n";
				else cout << "NO\n";}
			return 0;}
		ALL_THE(L,it) live[*it] =false;
		vector<int> Ln;
		ALL_THE(L,it) {
			ALL_THE(G[*it],jt) {
				D[*jt]--;
				S[*jt] +=A[*it];
				Sv[*jt].push_back(A[*it]);
				if(D[*jt] == 1 && live[*jt]) Ln.push_back(*jt);}
			}
		ALL_THE(Ln,it) {
			int a =S[*it]-A[*it], b =2*A[*it]-S[*it];
			if(a < 0 || b < 0 || 2*a > S[*it]) {
				cout << "NO\n";
				return 0;}
			sort(begin(Sv[*it]),end(Sv[*it]));
			if(a > S[*it]-Sv[*it].back()) {
				cout << "NO\n";
				return 0;}
			A[*it] =b;}
		n +=Ln.size();
		L =Ln;}
	cout << "YES\n";
	return 0;}

// look at my code
// my code is amazing

Submission Info

Judge Result