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:
import sys
sys.setrecursionlimit(500000)
N = int(input())
A = [0] + list(map(int, input().split()))
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

def dfs(v, p=0):
    a = A[v]
    b = []
    for u in E[v]:
        if u!=p:
            b.append(dfs(u, v))
    if len(b)==0:
        return a
    sum_b, max_b = sum(b), max(b)
    if a < 2*max_b-sum_b or a < 2*sum_b or a > sum_b:
        print("NO")
        exit()
    return 2 * a - sum_b

ans = dfs(1)
if (ans==0 and len(E[1])>1) or (ans==A[1] and len(E[1])==1):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
A = [0] + list(map(int, input().split()))
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

def dfs(v, p=0):
    a = A[v]
    b = []
    for u in E[v]:
        if u!=p:
            b.append(dfs(u, v))
    if len(b)==0:
        return a
    sum_b, max_b = sum(b), max(b)
    if a < 2*max_b-sum_b or a > sum_b:
        print("NO")
        exit()
    return 2 * a - sum_b

ans = dfs(1)
if (ans==0 and len(E[1])>1) or (ans==A[1] and len(E[1])==1):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
A = [0] + list(map(int, input().split()))
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

def dfs(v, p=0):
    a = A[v]
    b = []
    for u in E[v]:
        if u!=p:
            b.append(dfs(u, v))
    if len(b)==0:
        return a
    sum_b, max_b = sum(b), max(b)
    if a < max_b or a > sum_b:
        print("NO")
        exit()
    return 2 * a - sum_b

ans = dfs(1)
if (ans==0 and len(E[1])>1) or (ans==A[1] and len(E[1])==1):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
N = int(input())
A = [0] + list(map(int, input().split()))
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

def dfs(v, p=0):
    a = A[v]
    b = []
    for u in E[v]:
        if u!=p:
            b.append(dfs(u, v))
    if len(b)==0:
        return a
    sum_b, max_b = sum(b), max(b)
    if a < max_b or a > sum_b:
        print("NO")
        exit()
    return 2 * a - sum_b

ans = dfs(1)
if (ans==0 and len(E[1])>1) or (ans==1 and len(E[a])==1):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N = int(input())
As = list(map(int, input().split()))
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

def dfsTree(vNow):
    useds[vNow] = True
    for v2 in adjL[vNow]:
        if not useds[v2]:
            chlds[vNow].append(v2)
            dfsTree(v2)

vRoot = 0
chlds = [[] for v in range(N)]
useds = [False] * N
dfsTree(vRoot)

def dfs(vNow):
    if not chlds[vNow]:
        return As[vNow]
    cs = []
    for chld in chlds[vNow]:
        c = dfs(chld)
        if c == -1:
            return -1
        cs.append(c)
    sumC = sum(cs)
    T = 2*As[vNow] - sumC
    if T < 0:
        return -1
    cs.append(T)
    sumC += T
    if max(cs) <= sumC/2:
        return T
    else:
        return -1

ans = dfs(vRoot)
if ans != -1:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N = int(input())
As = list(map(int, input().split()))
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    adjL[A-1].append(B-1)
    adjL[B-1].append(A-1)

def dfsTree(vNow):
    useds[vNow] = True
    for v2 in adjL[vNow]:
        if not useds[v2]:
            chlds[vNow].append(v2)
            dfsTree(v2)

vRoot = 0
chlds = [[] for v in range(N)]
useds = [False] * N
dfsTree(vRoot)

def dfs(vNow):
    if not chlds[vNow]:
        return As[vNow]
    cs = []
    for chld in chlds[vNow]:
        c = dfs(chld)
        if c == -1:
            return -1
        cs.append(c)
    sumC = sum(cs)
    L = sumC-As[vNow]
    if min(sumC-max(cs), sumC//2) >= L:
        T = 2*As[vNow] - sum(cs)
        if vNow == vRoot and T+L != As[vRoot]:
            return -1
        else:
            return T
    else:
        return -1

ans = dfs(vRoot)
if ans != -1:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)
	adj[t-1].append(s-1)
par = [-1 for _ in range(n)]
aff = [0 for _ in range(n)]

def dfs(x, p):
	for v in adj[x]:
		if v == p:
			continue
		aff[x] += 1
		par[v] = x
		dfs(v, x)
	return
dfs(0, -1)
af_lis = [[] for _ in range(n)]
zero = [i for i in range(n) if aff[i] == 0]

def check(x):
	if af_lis[x] == []:
		af_lis[par[x]].append(a[x])
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	s, ma = sum(af_lis[x]), max(af_lis[x])
	if ma*2 > s:
		s_mi = ma
	else:
		s_mi = (s+1)//2
	if s_mi <= a[x] <= s:
		if par[x] == -1:
			if 2*a[x] != s:
				print("NO")
				sys.exit()
			else:
				return
		af_lis[par[x]].append(2*a[x] - s)
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	else:
		print("NO")
		sys.exit()
		return

while zero:
	check(zero.pop())

print("YES")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)
	adj[t-1].append(s-1)
par = [-1 for _ in range(n)]
aff = [0 for _ in range(n)]

def dfs(x, p):
	for v in adj[x]:
		if v == p:
			continue
		aff[x] += 1
		par[v] = x
		dfs(v, x)
	return
dfs(0, -1)
af_lis = [[] for _ in range(n)]
zero = [i for i in range(n) if aff[i] == 0]

def check(x):
	if af_lis[x] == []:
		af_lis[par[x]].append(a[x])
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	s, ma = sum(af_lis[x]), max(af_lis[x])
	if ma*2 > s:
		s_mi = ma
	else:
		s_mi = (s+1)//2
	if s_mi <= a[x] <= s:
		af_lis[par[x]].append(s - 2*(s-a[x]))
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	else:
		print("NO")
		sys.exit()
		return

while zero:
	check(zero.pop())

print("YES")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)
	adj[t-1].append(s-1)
par = [-1 for _ in range(n)]
aff = [0 for _ in range(n)]

def dfs(x, p):
	for v in adj[x]:
		if v == p:
			continue
		aff[x] += 1
		par[v] = x
		dfs(v, x)
	return
dfs(0, -1)
af_lis = [[] for _ in range(n)]
zero = [i for i in range(n) if aff[i] == 0]

def check(x):
	if af_lis[x] == []:
		af_lis[par[x]].append(a[x])
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	s, ma = sum(af_lis[x]), max(af_lis[x])
	if ma*2 > s:
		s_mi = ma
	else:
		s_mi = (s+1)//2
	if s_mi <= a[x] <= s:
		af_lis[par[x]].append(s - 2*(s-a[x]))
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	else:
		print("NO")
		sys.exit()
		return

while zero:
	check(zero.pop())

print("YES")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
A=[int(i) for i in 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)
Visited=[False]*N
B=[0]*N
def B_map(x):
  C=[]
  S=0
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      res=B_map(i)
      S+=res
      C.append(res)
  if len(C)==0:
    B[x]=A[x]
  elif len(C)==1:
    if A[x]==S:
      B[x]=S
    else:
      print("NO")
      exit()
  else:
    if S-A[x]<=min(S-max(C),S//2):
      B[x]=2*A[x]-S
    else:
      print("NO")
      exit()
  return B[x]
B_map(0)
if len(G[0])==1:
  if B[0]!=A[0]:
    print("NO")
    exit()
else:
  if B[0]!=0:
    print("NO")
    exit()
    
print("YES")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N=int(input())
A=[int(i) for i in 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)
Visited=[False]*N
B=[0]*N
def B_map(x):
  C=[]
  S=-1
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      res=B_map(i)
      if S<0:
        S=res
      else:
        S+=res
      C.append(res)
  if S<0:
    B[x]=A[x]
  else:
    M=max(max(C),sum(C)//2)
    T=2*A[x]-S
    if 0<=(S-T)//2<=M:
      B[x]=2*A[x]-S
    else:
      print("NO")
      exit()
    if x==0 and len(C)==1 and A[x]!=T:
      print("NO")
      exit()
    elif x==0 and len(C)>1 and T!=0:
      print("No")
      exit()
  return B[x]
B_map(0)
for i in range(N):
  if B[i]<0:
    print("NO")
    exit()
print("YES")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
a = list(map(int,input().split()))
g = [[]for i in range(n)]
for i in range(n-1):
  x,y = map(int,input().split())
  x-=1;y-=1
  g[x].append(y)
  g[y].append(x)
used = [0]*n
ue = [0]*n
for i in range(n):
  if len(g[i])== 1:
    ne = i
    break
huka = [0]*n
def dfs(x,y,z):
  if used[x]:
    return 0
  used[x] = 1
  huka[x] = y
  ue[x] = z
  for ix in g[x]:
    dfs(ix,y+1,x)
dfs(ne,0,-1)
for i in range(n):
  huka[i] = [huka[i],i]
huka.sort(key=lambda x:-x[0])
hen = [0]*(n)
for i in range(n-1):
  x = huka[i][1]
  if len(g[x]) == 1:
    hen[x] = a[x]
    hen[ue[x]] += hen[x]
    if hen[x] > a[ue[x]]:
      print("NO")
      exit()
    continue
  hen[x] = a[x]*2-hen[x]
  hen[ue[x]] += hen[x]
  if hen[x] > a[ue[x]]:
    print("NO")
    exit()
  if hen[x] <0:
    print("NO")
    exit()
if hen[ne] != a[ne]:
  print("NO")
else:
  print("YES")

Submission status: Wrong Answer

Solution code:
import sys
n=input()
sys.setrecursionlimit(n+1000)
value=map(int, raw_input().split())
adj=[[] for i in range(n)]
for i in range(n-1):
	a, b=map(int, raw_input().split())
	a, b=a-1, b-1
	adj[a].append(b)
	adj[b].append(a)
if n==2:
	print "YES" if value[0]==value[1] else "NO"
	exit()
def dfs(cur, father):
	if len(adj[cur])==1:
		return value[cur]
	cnt=0
	for to in adj[cur]:
		if to!=father:
			cnt+=dfs(to, cur)
	if value[cur]*2<cnt or cnt<value[cur]:
		raise Exception, value[cur], cnt
	return value[cur]*2-cnt
for i in range(n):
	if len(adj[i])>1:
		try:
			result=dfs(i, -1)
			print>>sys.stderr, result
			print "NO" if result else "YES"
		except Exception, e:
			print>>sys.stderr, e.message
			print "NO" 
		exit()

Submission status: Wrong Answer

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
dfs(0, -1)
if ok:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'

    def f(c, p):
        t = []
        ac = a[c]
        for d in e[c]:
            if d == p:
                continue
            r = f(d, c)
            if not r and r != 0:
                return
            t.append(r)

        if not t:
            return ac

        ts = sum(t)
        ma = min(ts//2, ts-max(t)) * 2
        at = ts - ac
        if at > ma or at < 0 or at > ac:
            return
        return ac - at

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        return 'NO'

    return 'NO'




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'

    def f(c, p):
        t = []
        ac = a[c]
        for d in e[c]:
            if d == p:
                continue
            r = f(d, c)
            if not r:
                return
            t.append(r)

        if not t:
            return ac

        ts = sum(t)
        ma = min(ts//2, ts-max(t)) * 2
        at = ts - ac
        if at > ma or at < 0 or at > ac:
            return
        return ac - at

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        return 'NO'

    return 'NO'




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'

    def f(c, p):
        t = []
        ac = a[c]
        for d in e[c]:
            if d == p:
                continue
            r = f(d, c)
            if not r:
                return
            t.append(r)

        if not t:
            return ac

        ts = sum(t)
        ma = min(ts//2, ts-max(t)) * 2
        at = ts - ac
        if at > ma or at < 0:
            return
        return ac - at

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        return 'NO'

    return 'NO'




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'

    def f(c, p):
        t = []
        ac = a[c]
        for d in e[c]:
            if d == p:
                continue
            r = f(d, c)
            if not r:
                return
            t.append(r)

        if not t:
            return ac

        ts = sum(t)
        ma = min(ts//2, max(t))
        at = ts - ac
        if at > ma or at < 0:
            return
        return ac - at

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        return 'NO'

    return 'NO'




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'

    def f(c, p):
        t = []
        ac = a[c]
        for d in e[c]:
            if d == p:
                continue
            r = f(d, c)
            if not r:
                return
            t.append(r)

        if not t:
            return ac

        ts = sum(t)
        ma = min(ts//2, ts-max(t))
        at = ts - ac
        if at > ma or at < 0:
            return
        return ac - at

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        return 'NO'

    return 'NO'




print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    def f(c,p):
        t = []
        ac = a[c]
        for b in e[c]:
            if b == p:
                continue
            res = f(b,c)
            if not res:
                return
            t.append(res)
        if not t:
            return ac
        tm = max(t)
        ts = sum(t)
        mi = max(tm*2 - ts, ts%2)
        tt = ac-(ts-ac)
        if (not (mi <= ac <= ts)) or (not (mi <= tt <= ts)):
            return
        return tt

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        break

    return 'NO'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    def f(c,p):
        t = []
        ac = a[c]
        for b in e[c]:
            if b == p:
                continue
            res = f(b,c)
            if not res:
                return
            t.append(res)
        if not t:
            return ac
        tm = max(t)
        ts = sum(t)
        mi = max(tm*2 - ts, ts%2)
        tt = ac-(ts-ac)
        if not (mi <= ac <= ts) or not (mi <= tt <= ts):
            return
        return tt

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        break

    return 'NO'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    def f(c,p):
        t = []
        ac = a[c]
        for b in e[c]:
            if b == p:
                continue
            res = f(b,c)
            if not res:
                return
            t.append(res)
        if not t:
            return ac
        tm = max(t)
        ts = sum(t)
        mi = tm*2 - ts
        tt = ac-(ts-ac)
        if not (mi <= ac <= ts) or not (mi <= tt <= ts):
            return
        return tt

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        break

    return 'NO'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    if n == 2:
        if a[0] == a[1]:
            return 'YES'
        return 'NO'
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    def f(c,p):
        t = []
        ac = a[c]
        for b in e[c]:
            if b == p:
                continue
            res = f(b,c)
            if not res:
                return
            t.append(res)
        if not t:
            return ac
        tm = max(t)
        ts = sum(t)
        mi = tm*2 - ts
        tt = ac-(ts-ac)
        if not (mi <= ac <= ts):
            return
        return tt

    for i in range(n):
        if len(e[i]) == 1:
            continue
        r = f(i,-1)
        if r == 0:
            return 'YES'
        break

    return 'NO'


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        b,c = LI_()
        e[b].append(c)
        e[c].append(b)

    def f(c,p):
        t = []
        ac = a[c]
        for b in e[c]:
            if b == p:
                continue
            res = f(b,c)
            if not res:
                return
            t.append(res)
        if not t:
            return ac
        tm = max(t)
        ts = sum(t)
        mi = tm*2 - ts
        tt = ac-(ts-ac)
        if not (mi <= ac <= ts):
            return
        return tt

    r = f(0,-1)
    if len(e[0]) == 1:
        if r == a[0]:
            return 'YES'
        return 'NO'
    if r == 0:
        return 'YES'

    return 'NO'


print(main())

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=[]
    if cnt[now]==0:
        for to in g[now]:
            if to>now:
                idx=edge[(now,to)]
            else:
                idx=edge[(to,now)]
            sum_edge.append(cost[idx])
        #print cost
        if sum(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.append(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:
        sum_edge.sort(reverse=True)
        mx=max(sum_edge[0],2*c[now]-sum(sum_edge))
        cost[nxidx]=2*c[now]-sum(sum_edge)
        if sum(sum_edge)-2*mx<0:
            ok=False
            break
        if sum(sum_edge)==0 and c[now]>0:
            ok=False
            break
        if cost[nxidx]<0:
            ok=False
            break
"""
for now in xrange(n):
    if len(g[now])==1:continue
    for nx in g[now]:
        if now>nx:
            now,nx=nx,now
        idx=edge[(now,nx)]
        if cost[idx]==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
        if sum_edge==0 and c[now]>0:
            ok=False
            break
        if cost[nxidx]<0:
            ok=False
            break
"""
for now in xrange(n):
    if len(g[now])==1:continue
    for nx in g[now]:
        if now>nx:
            now,nx=nx,now
        idx=edge[(now,nx)]
        if cost[idx]==0:
            ok=False
            break
"""
print "YES" if ok else "NO"