Problem:


Score : 700 points

Problem Statement

There is a tree with N vertices, numbered 1 through N.
The i-th of the N-1 edges connects vertices a_i and b_i.

Currently, there are A_i stones placed on vertex i.
Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:

Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices.
  Here, a leaf is a vertex of the tree whose degree is 1, and the selected leaves themselves are also considered as vertices on the path connecting them.

Note that the operation cannot be performed if there is a vertex with no stone on the path.

Constraints

2 ≦ N ≦ 10^5

1 ≦ a_i,b_i ≦ N

0 ≦ A_i ≦ 10^9

The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

If it is possible to remove all the stones from the vertices, print YES. Otherwise, print NO.

Sample Input 1

5
1 2 1 1 2
2 4
5 2
3 2
1 3

Sample Output 1

YES

All the stones can be removed, as follows:

Select vertices 4 and 5. Then, there is one stone remaining on each vertex except 4.

Select vertices 1 and 5. Then, there is no stone on any vertex.

Sample Input 2

3
1 2 1
1 2
2 3

Sample Output 2

NO

Sample Input 3

6
3 2 2 2 2 2
1 2
2 3
1 4
1 5
4 6

Sample Output 3

YES



Sample input:
5
1 2 1 1 2
2 4
5 2
3 2
1 3


Sample output:
YES

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(raw_input())
c=map(int,raw_input().split())
if n==2:
    if c[0]==c[1]:
        print "YES"
    else:
        print "NO"
    exit()

g=[[] for _ in xrange(n)]
cnt=[0]*n
edge={}
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    if a>b:
        a,b=b,a
    g[a].append(b)
    g[b].append(a)
    cnt[a]+=1
    cnt[b]+=1
    edge[(a,b)]=i
cost=[0]*(n-1)
used=[False]*(n-1)
leaf=deque([])
for i in xrange(n):
    if cnt[i]==1:
        leaf.append(i)
used=[False]*(n-1)
ok=True
while len(leaf)>0:
    now=leaf.popleft()
    sum_edge=0
    if cnt[now]==0:
        for to in g[now]:
            if to>now:
                idx=edge[(now,to)]
            else:
                idx=edge[(to,now)]
            sum_edge+=cost[idx]
        #print cost
        if sum_edge!=2*c[now]:
            ok=False
            break
        continue
    for to in g[now]:
        if to>now:
            idx=edge[(now,to)]
        else:
            idx=edge[(to,now)]
        if used[idx]:
            sum_edge+=cost[idx]
            continue
        else:
            nx=to
            nxidx=idx
    used[nxidx]=True
    cnt[nx]-=1
    if cnt[nx]==1:
        leaf.append(nx)
    if len(g[now])==1:
        cost[nxidx]=c[now]
    else:
        cost[nxidx]=2*c[now]-sum_edge
        if cost[nxidx]<0:
            ok=False
            break
print "YES" if ok else "NO"

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(raw_input())
c=map(int,raw_input().split())
if n==2:
    if c[0]==c[1]:
        print "YES"
    else:
        print "NO"
    exit()

g=[[] for _ in xrange(n)]
cnt=[0]*n
edge={}
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    if a>b:
        a,b=b,a
    g[a].append(b)
    g[b].append(a)
    cnt[a]+=1
    cnt[b]+=1
    edge[(a,b)]=i
cost=[0]*(n-1)
used=[False]*(n-1)
leaf=deque([])
for i in xrange(n):
    if cnt[i]==1:
        leaf.append(i)
used=[False]*(n-1)
ok=True
while len(leaf)>0:
    now=leaf.popleft()
    sum_edge=0
    if cnt[now]==0:
        for to in g[now]:
            if to>now:
                idx=edge[(now,to)]
            else:
                idx=edge[(to,now)]
            sum_edge+=cost[idx]
        #print cost
        if sum_edge!=2*c[now]:
            ok=False
            break
        continue
    for to in g[now]:
        if to>now:
            idx=edge[(now,to)]
        else:
            idx=edge[(to,now)]
        if used[idx]:
            sum_edge+=cost[idx]
            continue
        else:
            nx=to
            nxidx=idx
    used[nxidx]=True
    cnt[nx]-=1
    if cnt[nx]==1:
        leaf.append(nx)
    if len(g[now])==1:
        cost[nxidx]=c[now]
    else:
        cost[nxidx]=2*c[now]-sum_edge
print "YES" if ok else "NO"

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(raw_input())
c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
cnt=[0]*n
edge={}
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    if a>b:
        a,b=b,a
    if c[a]==0 and c[b]==0:continue
    g[a].append(b)
    g[b].append(a)
    cnt[a]+=1
    cnt[b]+=1
    edge[(a,b)]=i
cost=[0]*(n-1)
used=[False]*(n-1)
leaf=deque([])
for i in xrange(n):
    if cnt[i]==1:
        leaf.append(i)
used=[False]*(n-1)
ok=True
while len(leaf)>0:
    now=leaf.popleft()
    sum_edge=0
    if cnt[now]==0:
        for to in g[now]:
            if to>now:
                idx=edge[(now,to)]
            else:
                idx=edge[(to,now)]
            sum_edge+=cost[idx]
        if sum_edge!=2*c[now]:
            ok=False
            break
        continue
    for to in g[now]:
        if to>now:
            idx=edge[(now,to)]
        else:
            idx=edge[(to,now)]
        if used[idx]:
            sum_edge+=cost[idx]
            continue
        else:
            nx=to
            nxidx=idx
    used[nxidx]=True
    cnt[nx]-=1
    if cnt[nx]==1:
        leaf.append(nx)
    if len(g[now])==1:
        cost[nxidx]=c[now]
    else:
        cost[nxidx]=2*c[now]-sum_edge
print "YES" if ok else "NO"

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(raw_input())
c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
cnt=[0]*n
edge={}
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    if a>b:
        a,b=b,a
    if c[a]==0 and c[b]==0:continue
    if c[a]==0 or c[b]==0:
        print "NO"
        exit()
    g[a].append(b)
    g[b].append(a)
    cnt[a]+=1
    cnt[b]+=1
    edge[(a,b)]=i
cost=[0]*(n-1)
used=[False]*(n-1)
leaf=deque([])
for i in xrange(n):
    if cnt[i]==1:
        leaf.append(i)
used=[False]*(n-1)
ok=True
while len(leaf)>0:
    now=leaf.popleft()
    sum_edge=0
    if cnt[now]==0:
        for to in g[now]:
            if to>now:
                idx=edge[(now,to)]
            else:
                idx=edge[(to,now)]
            sum_edge+=cost[idx]
        if sum_edge!=2*c[now]:
            ok=False
            break
        continue
    for to in g[now]:
        if to>now:
            idx=edge[(now,to)]
        else:
            idx=edge[(to,now)]
        if used[idx]:
            sum_edge+=cost[idx]
            continue
        else:
            nx=to
            nxidx=idx
    used[nxidx]=True
    cnt[nx]-=1
    if cnt[nx]==1:
        leaf.append(nx)
    if len(g[now])==1:
        cost[nxidx]=c[now]
    else:
        cost[nxidx]=2*c[now]-sum_edge
print "YES" if ok else "NO"

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(raw_input())
c=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
cnt=[0]*n
edge={}
for i in xrange(n-1):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    if a>b:
        a,b=b,a
    g[a].append(b)
    g[b].append(a)
    edge[(a,b)]=i
    cnt[a]+=1
    cnt[b]+=1
leaf=deque([])
used=[False]*(n-1)
for i in xrange(n):
    if cnt[i]==1:
        leaf.append(i)
cost=[-1]*(n-1)
used=[False]*(n-1)
ok=True
while len(leaf)>0:
    now=leaf.popleft()
    sum_edge=0
    if cnt[now]==0:
        for to in g[now]:
            if to>now:
                idx=edge[(now,to)]
            else:
                idx=edge[(to,now)]
            sum_edge+=cost[idx]
        if sum_edge!=2*c[now]:
            ok=False
            break
        continue
    for to in g[now]:
        if to>now:
            idx=edge[(now,to)]
        else:
            idx=edge[(to,now)]
        if used[idx]:
            sum_edge+=cost[idx]
            continue
        else:
            nx=to
            nxidx=idx
    used[nxidx]=True
    cnt[nx]-=1
    if cnt[nx]==1:
        leaf.append(nx)
    if len(g[now])==1:
        cost[nxidx]=c[now]
    else:
        cost[nxidx]=2*c[now]-sum_edge
print "YES" if ok else "NO"

Submission status: Wrong Answer

Solution code:
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 status: Wrong Answer

Solution code:
import copy
def traverse(N,A,mm,root):
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
	
	start=root
	for i in range(start,N+1):
		if len(m[i])==1 and A[i]>0:
			root=i
			break
	
	eerror=False
	t[root]=2*A[root]
	r=root
	i=m[root].pop()
	rp[i]=r
	
	
	if r in m[i]:
		m[i].remove(r)
	if len(m[i])==0:
		t[i]=A[i]
	else:
		t[i]=2*A[i]
	
	while i!=root:
		#print(r,t[r],m[r],rp[r],'->',i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			r=i
			i=rp[i]
			t[i]-=t[r]
			if t[i]<0:
				eerror=True
				break
		else:
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
				
			if r in m[i]:
				m[i].remove(r)
			if len(m[i])==0:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
				
	#print(r,t[r],m[r],'->',i,t[i],m[i],rp[i])
	
	if t[r]==A[root] and eerror==False:
		return(0)
	else:
		return(root)
		
		
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()]
	m[l[0]]+=[l[1]]
	m[l[1]]+=[l[0]]

		
root=1
while root>=1 and root<=N:
	#print(root)
	root=traverse(N,A,m,root)
	if root==0:
		break
	#print(root)
	root+=1

if root==0:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
N= int(input())
A=[[]]
for x in input().split():
	A.extend([int(x)])

m=[]
t=[]
rp=[]

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

for i in range(N-1):
	l=[int(xx) for xx in input().split()]
	m[l[0]]+=[l[1]]
	m[l[1]]+=[l[0]]
	
for i in range(1,N+1):
	if len(m[i])==1:
		root=i

r=root
i=m[root].pop()
rp[i]=r
if r in m[i]:
	m[i].remove(r)
if len(m[i])==0:
	t[i]=A[i]
else:
	t[i]=2*A[i]

while i!=root:
	#print(r,t[r],m[r],rp[r],'->',i,t[i],m[i],rp[i])
	
	if len(m[i])==0:
		r=i
		i=rp[i]
		t[i]-=t[r]
	else:
		r=i
		i=m[i].pop()
		if rp[i]==0:
			rp[i]=r
			
		if r in m[i]:
			m[i].remove(r)
		if len(m[i])==0:
			t[i]=A[i]
		else:
			t[i]=2*A[i]
			
#print(r,t[r],m[r],'->',i)					
if t[r]==A[root]:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:

N= int(input())

A=[[]]+[int(x) for x in input().split()]

L=[]
for i in range(N-1):
	L.extend([[int(xx)for xx in input().split()]])

m=[]
t=[]
rp=[]
for i in range(N+1):
	m.extend([[]])
	t.extend([0])
	rp.extend([0])
	
for l in L:
	m[l[0]]+=[l[1]]
	m[l[1]]+=[l[0]]
	
for i in range(N):
	if len(m[i])==1:
		break
root=i

r=root
i=m[root].pop()
rp[i]=r
if r in m[i]:
	m[i].remove(r)
if len(m[i])==0:
	t[i]=A[i]
else:
	t[i]=2*A[i]

while i!=root:
	
	if len(m[i])==0:
		r=i
		i=rp[i]
		t[i]-=t[r]
	else:
	
		r=i
		i=m[i].pop()
		rp[i]=r
		if r in m[i]:
			m[i].remove(r)
		if len(m[i])==0:
			t[i]=A[i]
		else:
			t[i]=2*A[i]
				
if t[r]==A[root]:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
def TT(A=[],lines=[],ones=[],me=0,parent=0):
	sl=0
	if me in ones and parent==0:
		for a in lines:
			if a[0]==me:
				sl+=TT(A,lines,ones,a[1],me)
			elif a[1]==me:
				sl+=TT(A,lines,ones,a[0],me)
		if sl==0:
			return(A[me])
		else:
			return(A[me]*2-sl)
				
#	elif [me,parent] not in lines and [parent,me] not in lines:
#		return(0)
	else:
		for a in lines:
			if a[0]==me and a[1]!=parent:
				sl+=TT(A,lines,ones,a[1],me)
			elif a[1]==me and a[0]!=parent:
				sl+=TT(A,lines,ones,a[0],me)
		
		if sl==0:
			return(A[me])
		else:
			return(A[me]*2-sl)
			

N= int(input())

A=[[]]+[int(x) for x in input().split()]

L=[]
for i in range(N-1):
	L=L+[[int(xx)for xx in input().split()]]

LF=[x for y in L for x in y]
LF1= [x for x in LF if LF.count(x)==1]

mm=min(LF1)
if TT(A,L,LF1,mm)==A[mm]:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
def TT(A=[],lines=[],me=0,parent=0):
	sl=0
	if [x for y in lines for x in y].count(me)==1 and parent==0:
		for a in lines:
			if a[0]==me:
				sl+=TT(A,lines,a[1],me)
			elif a[1]==me:
				sl+=TT(A,lines,a[0],me)
		if sl==0:
			return(A[me])
		else:
			return(A[me]*2-sl)
				
	elif [me,parent] not in lines and [parent,me] not in lines:
		return(0)
	else:
		for a in lines:
			if a[0]==me and a[1]!=parent:
				sl+=TT(A,lines,a[1],me)
			elif a[1]==me and a[0]!=parent:
				sl+=TT(A,lines,a[0],me)
		
		if sl==0:
			return(A[me])
		else:
			return(A[me]*2-sl)
			

N= int(input())

A=[[]]+[int(x) for x in input().split()]

L=[]
for i in range(N-1):
   L=L+[[int(xx)for xx in input().split()]]

LF=[x for y in L for x in y]
LF1= [x for x in LF if LF.count(x)==1]

mm=min(LF1)
if TT(A,L,mm)==A[mm]:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
def T(A=[],lines=[],me=0,parent=0):
	if [x for y in lines for x in y].count(me)==1 and parent==0:
		for a in lines:
			if a[0]==me:
				return(T(A,lines,a[1],me))
			elif a[1]==me:
				return(T(A,lines,a[0],me))
	elif [me,parent] not in lines and [parent,me] not in lines:
		return(0)
	else:
		sl=0
		for a in lines:
			if a[0]==me and a[1]!=parent:
				sl=sl+T(A,lines,a[1],me)
			elif a[1]==me and a[0]!=parent:
				sl=sl+T(A,lines,a[0],me)
		
		if sl==0:
			return(A[me-1])
		else:
			return(A[me-1]*2-sl)

N= int(input())

A=[int(x) for x in input().split()]

L=[]
for i in range(N-1):
   L=L+[[int(xx)for xx in input().split()]]

LF=[x for y in L for x in y]
LF1= [x for x in LF if LF.count(x)==1]

if T(A,L,min(LF1))==A[min(LF1)-1]:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
def T(A=[],lines=[],me=0,parent=0):
	if [x for y in lines for x in y].count(me)==1 and parent==0:
		for a in lines:
			if a[0]==me:
				return(T(A,lines,a[1],me))
			elif a[1]==me:
				return(T(A,lines,a[0],me))
	elif [me,parent] not in lines and [parent,me] not in lines:
		return(0)
	else:
		sl=0
		for a in lines:
			if a[0]==me and a[1]!=parent:
				sl=sl+T(A,lines,a[1],me)
			elif a[1]==me and a[0]!=parent:
				sl=sl+T(A,lines,a[0],me)
		
		if sl==0:
			return(A[me-1])
		else:
			return(A[me-1]*2-sl)

N= int(input())

A=[int(x) for x in input().split()]

L=[]
for i in range(N-1):
   L=L+[[int(xx)for xx in input().split()]]

LF=[x for y in L for x in y]
LF1= [x for x in LF if LF.count(x)==1]

if T(A,L,min(LF1))==A[min(LF1)]-1:
	print('YES')
else:
	print('NO')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

n = int(input())
a = readln(' ')
e = [set([]) for i in range(0,n+1)]
for i in range(1,n):
    s = readln(' ')
    e[s[0]].add(s[1])
    e[s[1]].add(s[0])
rt = 1
now = n
v = [0 for i in range(0,n+1)]
q = v[:]
q[now] = rt
v[rt] = 1
for i in range(1,n):
    s = q[n-i+1]
    for p in e[s]:
        if v[p] == 0:
            v[p] = 1
            now = now - 1
            q[now] = p

res = 'YES'
up = [0 for i in range(0,n+1)]
for i in range(1,n+1):
    k = q[i]
    if len(e[k]) == 1:
        sum = a[k-1]
    else:
        sum = a[k-1] * 2
    up[k] = sum
    for son in e[k]:
        up[k] = up[k] - up[son]
        if up[k] > a[k-1]: res = 'NO'
    if up[k] < 0:
        res = 'NO'
    if len(e[k]) > 1 and up[k] > a[k-1]:
        res = 'NO'

if up[rt] != 0 : res = 'NO'
print(res)

Submission status: Wrong Answer

Solution code:
print('NO')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

n = int(input())
a = readln(' ')
e = [set([]) for i in range(0,n+1)]
for i in range(1,n):
    s = readln(' ')
    e[s[0]].add(s[1])
    e[s[1]].add(s[0])
rt = 1
now = n
v = [0 for i in range(0,n+1)]
q = v[:]
q[now] = rt
v[rt] = 1
for i in range(1,n):
    s = q[n-i+1]
    for p in e[s]:
        if v[p] == 0:
            v[p] = 1
            now = now - 1
            q[now] = p

res = 'YES'
up = [0 for i in range(0,n+1)]
for i in range(1,n+1):
    k = q[i]
    if len(e[k]) == 1:
        sum = a[k-1]
    else:
        sum = a[k-1] * 2
    up[k] = sum
    for son in e[k]:
        up[k] = up[k] - up[son]
    if up[k] < 0:
        res = 'NO'
    if len(e[k]) > 1 and up[k] > a[k-1]:
        res = 'NO'
if up[rt] > 0 : res = 'NO'
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

n = int(input())
a = readln(' ')
e = [set([]) for i in range(0,n+1)]
for i in range(1,n):
    s = readln(' ')
    e[s[0]].add(s[1])
    e[s[1]].add(s[0])
rt = 1
for i in range(1,n+1):
    if len(e[i]) > 1:
        rt = i
now = n
v = [0 for i in range(0,n+1)]
q = v[:]
f = v[:]
q[now] = rt
v[rt] = 1
for i in range(1,n):
    s = q[n-i+1]
    for p in e[s]:
        if v[p] == 0:
            v[p] = 1
            now = now - 1
            q[now] = p
            e[p].remove(s)
            f[p] = s

res = 'YES'
up = [0 for i in range(0,n+1)]
for i in range(1,n+1):
    k = q[i]
    if len(e[k]) == 0:
        up[k] = a[k-1]
    else:
        up[k] = a[k-1] * 2
        for son in e[k]:
            up[k] = up[k] - up[son]
        if up[k] < 0:
            res = 'NO'
        if up[k] > a[k-1]:
            res = 'NO'
if up[rt] > 0 : res = 'NO'

if n == 2:
    if a[0] == a[1]:
        res = 'YES'
    else:
        res = 'NO'
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

n = int(input())
a = readln(' ')
e = [set([]) for i in range(0,n+1)]
for i in range(1,n):
    s = readln(' ')
    e[s[0]].add(s[1])
    e[s[1]].add(s[0])
rt = 0
for i in range(1,n+1):
    if len(e[i]) > 1:
        rt = i
now = n
v = [0 for i in range(0,n+1)]
q = v[:]
f = v[:]
q[now] = rt
v[rt] = 1
for i in range(1,n):
    s = q[n-i+1]
    for p in e[s]:
        if v[p] == 0:
            v[p] = 1
            now = now - 1
            q[now] = p
            e[p].remove(s)
            f[p] = s

res = 'YES'
up = [0 for i in range(0,n+1)]
for i in range(1,n+1):
    k = q[i]
    if len(e[k]) == 0:
        up[k] = a[k-1]
    else:
        up[k] = a[k-1] * 2
        for son in e[k]:
            up[k] = up[k] - up[son]
        if up[k] < 0:
            res = 'NO'
        if up[k] > a[k-1]:
            res = 'NO'
if up[rt] > 0 : res = 'NO'
print(res)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [0] + map(int, stdin.readline().split(), repeat(10, n))
    m = 2 * (n - 1)
    dat = map(int, stdin.read().split(), repeat(10, m))
    j = 0
    xt = [None] * m
    la = [None] * (n + 1)
    deg = [0] * (n + 1)
    if n == 2:
        print "YES" if a[1] == a[2] else "NO"
        return
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        xt[j] = la[y]
        deg[x] += 1
        deg[y] += 1
        la[x] = j + 1
        la[y] = j
        j += 2
    st = []
    pu = st.append
    po = st.pop
    for i in xrange(1, n + 1):
        if deg[i] != 1:
            r = i
            break
    pu(r)
    col = [0] * (n + 1)
    sd = [0] * (n + 1)
    while st:
        x = po()
        if col[x] == 0:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(z)
                y = xt[y]
        elif deg[x] > 1:
            col[x] = 2
            y = la[x]
            ss = 0
            ms = 0
            while y is not None:
                if col[dat[y]] == 2:
                    z = sd[dat[y]]
                    ss += z
                    if ms < z:
                        ms = z
                y = xt[y]
            if a[x] > ss or ss > 2 * a[x]:
                print "NO"
                return
            sd[x] = 2 * a[x] - ss
            if (a[x] - sd[x]) / 2 > min(ms, ss / 2):
                print "NO"
                return
        else:
            col[x] = 2
            sd[x] = a[x]
    print "YES" if sd[r] == 0 else "NO"
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [0] + map(int, stdin.readline().split(), repeat(10, n))
    m = 2 * (n - 1)
    dat = map(int, stdin.read().split(), repeat(10, m))
    j = 0
    xt = [None] * m
    la = [None] * (n + 1)
    deg = [0] * (n + 1)
    if n == 2:
        print "YES" if a[1] == a[2] else "NO"
        return
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        xt[j] = la[y]
        deg[x] += 1
        deg[y] += 1
        la[x] = j + 1
        la[y] = j
        j += 2
    st = []
    pu = st.append
    po = st.pop
    for i in xrange(1, n + 1):
        if deg[i] != 1:
            r = i
            break
    pu(r)
    col = [0] * (n + 1)
    sd = [0] * (n + 1)
    while st:
        x = po()
        if col[x] == 0:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(z)
                y = xt[y]
        elif deg[x] > 1:
            col[x] = 2
            y = la[x]
            ss = 0
            ms = 0
            while y is not None:
                if col[dat[y]] == 2:
                    z = sd[dat[y]]
                    ss += z
                    if ms < z:
                        ms = z
                y = xt[y]
            if ss > 2 * a[x]:
                print "NO"
                return
            sd[x] = 2 * a[x] - ss
            if (a[x] - sd[x]) / 2 > min(ms, ss / 2):
                print "NO"
                return
        else:
            col[x] = 2
            sd[x] = a[x]
    print "YES" if sd[r] == 0 else "NO"
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [0] + map(int, stdin.readline().split(), repeat(10, n))
    m = 2 * (n - 1)
    dat = map(int, stdin.read().split(), repeat(10, m))
    j = 0
    xt = [None] * m
    la = [None] * (n + 1)
    deg = [0] * (n + 1)
    if n == 2:
        print "YES" if a[1] == a[2] else "NO"
        return
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        xt[j] = la[y]
        deg[x] += 1
        deg[y] += 1
        la[x] = j + 1
        la[y] = j
        j += 2
    st = []
    pu = st.append
    po = st.pop
    for i in xrange(1, n + 1):
        if deg[i] != 1:
            r = i
            break
    pu(r)
    col = [0] * (n + 1)
    sd = [0] * (n + 1)
    while st:
        x = po()
        if col[x] == 0:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(dat[y])
                y = xt[y]
        elif deg[x] > 1:
            y = la[x]
            ss = 0
            ms = 0
            while y is not None:
                z = sd[dat[y]]
                ss += z
                if ms < z:
                    ms = z
                y = xt[y]
            if ss > 2 * a[x]:
                print "NO"
                return
            sd[x] = 2 * a[x] - ss
            if (a[x] - sd[x]) / 2 > min(ms, ss / 2):
                print "NO"
                return
        else:
            sd[x] = a[x]
    print "YES" if sd[r] == 0 else "NO"
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [0] + map(int, stdin.readline().split(), repeat(10, n))
    m = 2 * (n - 1)
    dat = map(int, stdin.read().split(), repeat(10, m))
    j = 0
    xt = [None] * m
    la = [None] * (n + 1)
    deg = [0] * (n + 1)
    if n == 2:
        print "YES" if a[1] == a[2] else "NO"
        return
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        xt[j] = la[y]
        deg[x] += 1
        deg[y] += 1
        la[x] = j + 1
        la[y] = j
        j += 2
    st = []
    pu = st.append
    po = st.pop
    for i in xrange(1, n + 1):
        if deg[i] != 1:
            r = i
            break
    pu(r)
    col = [0] * (n + 1)
    sd = [0] * (n + 1)
    while st:
        x = po()
        if col[x] == 0:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(dat[y])
                y = xt[y]
        elif deg[x] > 1:
            y = la[x]
            ss = 0
            ms = 0
            while y is not None:
                z = sd[dat[y]]
                ss += z
                if ms < z:
                    ms = z
                y = xt[y]
            print ss, ms, a[x]
            if ss > 2 * a[x]:
                print "NO"
                return
            sd[x] = 2 * a[x] - ss
            if (a[x] - sd[x]) / 2 > min(ms, ss / 2):
                print "NO"
                return
        else:
            sd[x] = a[x]
    print "YES" if sd[r] == 0 else "NO"
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
edges = {n+1:[] for n in range(N)}
         
for n in range(N-1):
    a, b = [int(n) for n in input().split()]
    edges[a].append(b)
    edges[b].append(a)

ends = [k for k, v in edges.items() if len(v)==1]
roots = set()
        
def search(past, p):
    dest = edges[p]
    if len(dest) == 1:
        past.append(p)
        roots.update(past)
    else :
        for i in range(dest):
            if dest[i] != past[-1]:
                past.append(p)
                search(past, dest[i])

for end in ends:
    search([end], edges[end][0])

# 全ての基底ベクトルはendsに収納されたので、このベクトルがはる空間にAが含まれるかどうかを検索したいだけの人生だった（敗北）

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    
    
def sub(u, p):
    if len(ns[u])==1 and p in ns[u]:
        return a[u]
    ub = 0
    mv = 0
    msum = 0
    for v in ns[u]:
        if p==v:
            continue
        val = sub(v, u)
        if val is None:
            return None
        mv = max(mv, val)
        msum += val
    lb = max(mv, msum//2)
    if not (lb<=a[u]<=msum):
#         print(u,lb, msum, mv)
        return None
    else:
        return a[u] - (msum-a[u])
if n==2:
    if a[0]==a[1]:
        print("YES")
    else:
        print("NO")
else:
    if len(ns[0])>1:
        ans = sub(0, -1)
    else:
        ans = sub(list(ns[0])[0], -1)

    if ans is None or ans!=0:
        print("NO")
    else:
        print("YES")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
*A, = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

def calc(S):
    if not S:
        return 0
    S.sort(reverse=1)
    if S[0] > sum(S[1:]):
        return sum(S[1:])
    return sum(S)//2
ok = 1
def dfs(v, p):
    global ok
    c = A[v]
    S = []
    for w in G[v]:
        if w == p:
            continue
        S.append(dfs(w, v))
    if not S:
        return c
    d = calc(S)
    s = sum(S)
    k = s - c
    if not 0 <= k <= d:
        ok = 0
    return s - 2*k
import random
random.seed()
*r, = range(N)
random.shuffle(r)
d = {}
for i in range(min(3, N)):
    dfs(r[i], -1)

if ok:
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = [0] + map(int, stdin.readline().split(), repeat(10, n))
    m = 2 * (n - 1)
    dat = map(int, stdin.read().split(), repeat(10, m))
    j = 0
    xt = [None] * m
    la = [None] * (n + 1)
    deg = [0] * (n + 1)
    if n == 2:
        print "YES" if a[1] == a[2] else "NO"
        return
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j+1] = la[x]
        xt[j] = la[y]
        deg[x] += 1
        deg[y] += 1
        la[x] = j + 1
        la[y] = j
        j += 2
    st = []
    pu = st.append
    po = st.pop
    for i in xrange(1, n + 1):
        if deg[i] != 1:
            r = i
            break
    pu(r)
    col = [0] * (n + 1)
    sd = [0] * (n + 1)
    while st:
        x = po()
        if col[x] == 0:
            col[x] = 1
            pu(x)
            y = la[x]
            while y is not None:
                z = dat[y]
                if not col[z]:
                    pu(z)
                y = xt[y]
        elif deg[x] > 1:
            col[x] = 2
            y = la[x]
            ss = 0
            ms = 0
            while y is not None:
                if col[dat[y]] == 2:
                    z = sd[dat[y]]
                    ss += z
                    if ms < z:
                        ms = z
                    y = xt[y]
            if ss > 2 * a[x]:
                print "NO"
                return
            sd[x] = 2 * a[x] - ss
            if (a[x] - sd[x]) / 2 > min(ms, ss / 2):
                print "NO"
                return
        else:
            col[x] = 2
            sd[x] = a[x]
    print "YES" if sd[r] == 0 else "NO"
main()