Submission #1164377

---

Source Code Expand

import copy

def traverse(N,A,mm):
	if N<2 or len(A)!=N+1 or len(mm)!=N+1:
		return(False)
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	c=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
		c.extend([[0]])
	
	start=1
	for i in range(start,N+1):
		if len(m[i])==1 and A[i]>0:
		#if A[i]>0:
			root=i
			break
	
	eerror=False
	if len(m[root]) in [0,1]:
		t[root]=A[root]
	else:
		t[root]=2*A[root]
	
	r=0
	i=root
	while not(i==root and len(m[i])==0):
		#print(i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			#print('back')
			c[i][0]=t[i]
			r=i
			i=rp[i]
			#print(i,t[i],m[i],rp[i])
			t[i]-=t[r]
			c[i].extend([t[r]])
			#print('minus')
			#print(c)
			if t[i]<0:
				return(False)
				#eerror=True
				#break
		else:
			#print('forward')
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
			#print(i,t[i],m[i],rp[i])	
			if len(m[i]) in [0,1]:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
			#print('plus')
			#print(i,t[i],m[i],rp[i])
			if r in m[i]:
				m[i].remove(r)
				#print('remove')
		
	
	for cc in c[1:]:
		cc_max=cc.index(max(cc))
		if len(cc)>2 and cc[cc_max]>sum([cc[i] for i in range(len(cc)) if i!=cc_max]):
			return(False)
			
	if t[root]==0 and eerror==False:
		return(True)
	else:
		return(False)
		
		
N= int(input())
A=[0]
for x in input().split():
	A.extend([int(x)])
	
m=[]

for i in range(N+1):
	m.extend([[]])

for i in range(N-1):
	l=[int(xx) for xx in input().split()]
	#l=[int(xx) for xx in L.pop()]
	if 0<l[0]<=N and 0<l[1]<=N:
		m[l[0]]+=[l[1]]
		m[l[1]]+=[l[0]]

		
if traverse(N,A,m):
	print('YES')
else:
	print('NO')
	

Submission Info

Judge Result