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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = [a*2 for a in A]
def dfs(v, par=-1):
  if T[v] == [par]:
    C[par] -= A[v]
    return True
  for nv in T[v]:
    if nv != par:
      if not dfs(nv, v):
        return False
  if C[v] < 0:
    return False
  if par == -1:
    if len(T[v]) == 1:
      return C[v] == A[v]
    return C[v] == 0
  C[par] -= C[v]
  return True
if dfs(0):
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


def check():
    stack = [0]
    checked = [False]*N
    need = [[] for _ in range(N)]
    Parent = [-1]*N
    while stack:
        p = stack.pop()
        if p >= 0:
            checked[p] = True
            stack.append(~p)
            for np in graph[p]:
                if not checked[np]:
                    Parent[np] = p
                    stack.append(np)
        else:
            p = ~p
            if len(need[p]) == 0:
                need[Parent[p]].append(A[p])
            elif len(need[p]) == 1:
                if need[p][0] != A[p]:
                    return False
                need[Parent[p]].append(A[p])
            else:
                kmax = sum(need[p])
                kmin = max(max(need[p]), (kmax+1)//2)
                if not kmin <= A[p] <= kmax:
                    return False
                need[Parent[p]].append(kmax-2*(kmax-A[p]))
    return True

print("YES" if check() else "NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
A = list(map(int,input().split()))
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

r = -1
for i in range(N):
    if len(es[i]) > 1:
        r = i
        break

def dfs(v,p=-1):
    if len(es[v]) == 1:
        return A[v]
    s = mxc = 0
    for to in es[v]:
        if to==p: continue
        c = dfs(to,v)
        s += c
        mxc = max(mxc,c)
    pair = s - A[v]
    ret = s - pair*2
    if pair < 0 or ret < 0 or (mxc*2 > s and pair > s - mxc):
        print('NO')
        exit()
    return ret

print('YES' if dfs(r)==0 else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
A = list(map(int,input().split()))
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

r = -1
for i in range(N):
    if len(es[i]) > 1:
        r = i
        break

def dfs(v,p=-1):
    if len(es[v]) == 1:
        return A[v]
    s = 0
    for to in es[v]:
        if to==p: continue
        s += dfs(to,v)
    pair = s - A[v]
    ret = s - pair*2
    if pair < 0 or ret < 0:
        print('NO')
        exit()
    return ret

print('YES' if dfs(r)==0 else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
if root == 0:
  if stone[0] == stone[1]:
    print("YES")
  else:
    print("NO")
  exit()
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x] or max(dp[x]) > stone[x]:
      flg = 0
    break
  elif dp[x]:
    if max(max(dp[x])*2,sum(dp[x])) > stone[x]*2 or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x] or max(dp[x]) > stone[x]:
      flg = 0
    break
  elif dp[x]:
    if max(max(dp[x])*2,sum(dp[x])) > stone[x]*2 or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x]:
      flg = 0
    break
  elif dp[x]:
    if max(max(dp[x])*2,sum(dp[x])) > stone[x]*2 or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x]:
      flg = 0
    break
  if dp[x]:
    if max(max(dp[x])*2,sum(dp[x])) > stone[x]*2 or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x]:
      flg = 0
    break
  if dp[x]:
    if max(max(dp[x]),sum(dp[x])/2) > stone[x] or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x]:
      flg = 0
    break
  if dp[x]:
    if max(dp[x]) > stone[x] or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
for i in range(2,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
deg[root] += 1
flg = 1
while stack:
  x = stack.pop()
  if x == root:
    if sum(dp[x]) != 2*stone[x]:
      flg = 0
    break
  if dp[x]:
    if max(dp[x]) > stone[x] or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
deg[1] += 1
if deg[1] == 2:
  leaf1 = 1
else:
  leaf1 = 0
for i in range(2,n+1):
  if deg[i] == 1:
    stack.append(i)
flg = 1
while stack:
  x = stack.pop()
  if x == 1:
    if leaf1:
      if sum(dp[x]) != stone[x]:
        flg = 0
    else:
      if sum(dp[x]) != 2*stone[x]:
        flg = 0
    break
  if dp[x]:
    if max(dp[x]) > stone[x] or stone[x] > sum(dp[x]):
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
n = int(input())
stone = [0]+list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
dp = [[] for i in range(n+1)]
deg = [0]*(n+1)
stack = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
deg[1] += 1
if deg[1] == 2:
  leaf1 = 1
else:
  leaf1 = 0
for i in range(2,n+1):
  if deg[i] == 1:
    stack.append(i)
flg = 1
while stack:
  x = stack.pop()
  if x == 1:
    if leaf1:
      if sum(dp[x]) != stone[x]:
        flg = 0
    else:
      if sum(dp[x]) != 2*stone[x]:
        flg = 0
    break
  if dp[x]:
    if max(dp[x]) > stone[x]:
      flg = 0
      break
    stone[x] = 2*stone[x]-sum(dp[x])
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(stone[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if flg:
  print("YES")
else:
  print("NO")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    if N == 2:
        if A[0] == A[1]:
            print('YES')
        else:
            print('NO')
        exit()

    for v in range(1, N+1):
        if len(adj[v]) != 1:
            v0 = v
            break

    # from collections import deque
    que = deque()
    que.append(v0)
    seen = [-1] * (N+1)
    seen[v0] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)

    for v in reversed(seq):
        if not child[v]:
            continue
        L = []
        for u in child[v]:
            L.append(A[u-1])
        if len(L) == 1:
            if L[0] != A[v-1]:
                print('NO')
                exit()
            continue
        s = sum(L)
        m = max(L)
        if s < A[v-1]:
            print('NO')
            exit()
        if A[v-1] < (s+1) // 2:
            print('NO')
            exit()
        if A[v-1] < m:
            print('NO')
            exit()
        A[v-1] = 2 * A[v-1] - s

    print(A, v0)
    if A[v0-1]:
        print('NO')
    else:
        print('YES')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    if N == 2:
        if A[0] == A[1]:
            print('YES')
        else:
            print('NO')
        exit()
    
    for v in range(1, N+1):
        if len(adj[v]) != 1:
            v0 = v
            break

    # from collections import deque
    que = deque()
    que.append(v0)
    seen = [-1] * (N+1)
    seen[v0] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)

    for v in reversed(seq):
        if not child[v]:
            if A[v-1] == 0:
                print('NO')
                exit()
            continue
        L = []
        for u in child[v]:
            L.append(A[u-1])
        if len(L) == 1:
            if L[0] != A[v-1]:
                print('NO')
                exit()
            continue
        s = sum(L)
        m = max(L)
        if s < A[v-1]:
            print('NO')
            exit()
        if A[v-1] < (s+1) // 2:
            print('NO')
            exit()
        if A[v-1] < m:
            print('NO')
            exit()
        A[v-1] = 2 * A[v-1] - s

    if A[v0-1]:
        print('NO')
    else:
        print('YES')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    for v in range(1, N+1):
        if len(adj[v]) == 1:
            v0 = v
            break

    # from collections import deque
    que = deque()
    que.append(v0)
    seen = [-1] * (N+1)
    seen[v0] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)

    for v in reversed(seq):
        if not child[v]:
            if A[v-1] == 0:
                print('NO')
                exit()
            continue
        L = []
        for u in child[v]:
            L.append(A[u-1])
        if len(L) == 1:
            if L[0] != A[v-1]:
                print('NO')
                exit()
            continue
        s = sum(L)
        m = max(L)
        if s < A[v-1]:
            print('NO')
            exit()
        if A[v-1] < (s+1) // 2:
            print('NO')
            exit()
        if A[v-1] < m:
            print('NO')
            exit()
        A[v-1] = 2 * A[v-1] - s

    print('YES')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    # from collections import deque
    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)

    for v in reversed(seq):
        if not child[v]:
            if A[v-1] == 0:
                print('NO')
                exit()
            continue
        L = []
        for u in child[v]:
            L.append(A[u-1])
        if len(L) == 1:
            if L[0] != A[v-1]:
                print('NO')
                exit()
            continue
        s = sum(L)
        m = max(L)
        if s < A[v-1]:
            print('NO')
            exit()
        if A[v-1] < (s+1) // 2:
            print('NO')
            exit()
        if A[v-1] < m:
            print('NO')
            exit()
        A[v-1] = 2 * A[v-1] - s

    print('YES')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter 

def calc(A):
    s = sum(A)
    ma = max(A)
    if 2*ma > s:
        return s - ma
    return s//2

def check():
    candi = [[] for _ in range(N)]
    for l in L[:0:-1]:
        p = P[l]
        if candi[l]:
            x = sum(candi[l]) - A[l]
            y = A[l] - x
            if 0 <= y <= calc(candi[l]):
                return 'NO'
        else:
            x = 0
            y = A[l]
        candi[p].append(y)
    x = sum(candi[root]) - A[root]
    y = A[root] - x
    if candi[root]:
        if not 0 <= sum(candi[root]) - A[root] <= calc(candi[root]):
            return 'NO'
    if y:
        return 'NO'         
    return 'YES'

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
A = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
Dim = [0]*N
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a] += 1
    Dim[b] += 1

if N == 2:
    ans = 'YES' if A[0] == A[1] else 'NO'
else:
    root = Dim.index(max(Dim))
    P, L = parorder(Edge, root)
    C = getcld(P)
    ans = check()

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter 

def calc(A):
    s = sum(A)
    ma = max(A)
    if 2*ma > s:
        return s - ma
    return s//2

def check():
    candi = [[] for _ in range(N)]
    for l in L[:0:-1]:
        p = P[l]
        if candi[l]:
            x = sum(candi[l]) - candi[l]
            y = A[l] - x
            if 0 <= y <= calc(candi[l]):
                return 'NO'
        else:
            x = 0
            y = A[l]
    x = sum(candi[0]) - A[0]
    y = A[0] - x
    if candi[0]:
        if not 0 <= sum(candi[0]) - A[0] <= calc(candi[0]):
                return 'NO'
    if y:
        return 'NO'
    return 'YES'

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
A = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

P, L = parorder(Edge, 0)
C = getcld(P)
print(check())

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter 

def calc(A):
    s = sum(A)
    ma = max(A)
    if 2*ma > s:
        return s - ma
    return s//2

def check():
    for l in L[:0:-1]:
        p = P[l]
        if candi[l]:
            if not 0 <= sum(candi[l]) - A[l] <= calc(candi[l]):
                return 'NO'
            candi[p].append(2*A[l] - sum(candi[l]))
        else:
            candi[p].append(A[l])
    if candi[0]:
        if not 0 <= sum(candi[0]) - A[0] <= calc(candi[0]):
                return 'NO'
    return 'YES'
def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
A = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

P, L = parorder(Edge, 0)
C = getcld(P)

dp = A[:]
candi = [[] for _ in range(N)]
print(check())

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, A, use, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, A, use, Wlist, visit, i)
			Wlist[node].append(use[i])

	#抜けの処理
	if Wlist[node] == []:
		use[node] = A[node]
	else:
		Z = sum(Wlist[node])
		if max(max(Wlist[node]), (Z + 1) // 2) <= A[node] and A[node] <= Z:
			use[node] = 2 * A[node] - Z
		else:
			use[node] = 2 * A[node] - Z
			judge = "NO"

#処理内容
def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#面倒なケース
	if N == 2:
		if A[0] == A[1]:
			print("YES")
			return
		else:
			print("NO")
			return

	s = None
	for i in range(N):
		if len(G.graph[i]) >= 2:
			s = i
			break
	#DFS
	judge = "YES"
	use = [None] * N
	Wlist = [[] for i in range(N)]
	visit = ["No"] * N
	visit[s] = "Yes"
	DFS(G, A, use, Wlist, visit, s)
	# print(use)

	if use[s] != 0:
		judge = "NO"
	#答え
	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)



INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
A = LI()
graph = [[] for _ in range(n)]
for u, v in LIR(n - 1):
    graph[u - 1] += [v - 1]
    graph[v - 1] += [u - 1]

if n == 2:
    x, y = A
    answer = 'YES' if x == y else 'NO'
    print(answer)
    exit()


def dfs(v, parent=None):
    x = A[v]
    if len(graph[v]) == 1:
        return x
    s = 0
    for w in graph[v]:
        if w == parent:
            continue
        ret = dfs(w, v)
        if ret == None:
            return None
        if x < ret:
            return None
        s += ret
    if 2 * x - s > s:
        return None
    if 2 * x < s:
        return None
    return 2 * x - s


ret = dfs(0)
bl = (ret == 0)

answer = 'YES' if bl else 'NO'
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
A = [int(x) for x in input().split()]
UV = [[int(x)-1 for x in row.split()] for row in sys.stdin.readlines()]

if N == 2:
    x,y = A
    answer = 'YES' if x == y else 'NO'
    print(answer)
    exit()

graph = [[] for _ in range(N)]
for u,v in UV:
    graph[u].append(v)
    graph[v].append(u)

def dfs(v,parent=None):
    x = A[v]
    if len(graph[v]) == 1:
        return x
    s = 0
    for w in graph[v]:
        if w == parent:
            continue
        ret = dfs(w,v)
        if ret == None:
            return None
        if x < ret:
            print('--',x,ret)
            return None
        s += ret
    if 2*x-s > s:
        return None
    if 2*x < s:
        return None
    return 2*x-s

v=0
while len(graph[v]) == 1:
    v += 1

ret = dfs(v)
bl = (ret == 0)

answer = 'YES' if bl else 'NO'
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
A = [int(x) for x in input().split()]
UV = [[int(x)-1 for x in row.split()] for row in sys.stdin.readlines()]

if N == 2:
    x,y = A
    answer = 'YES' if x == y else 'NO'
    print(answer)
    exit()

graph = [[] for _ in range(N)]
for u,v in UV:
    graph[u].append(v)
    graph[v].append(u)

def dfs(v,parent=None):
    x = A[v]
    if len(graph[v]) == 1:
        return x
    s = 0
    for w in graph[v]:
        if w == parent:
            continue
        ret = dfs(w,v)
        if ret == None:
            return None
        if x < ret:
            print('--',x,ret)
            return None
        s += ret
    if 2*x < s:
        return None
    return 2*x-s

v=0
while len(graph[v]) == 1:
    v += 1

ret = dfs(v)
bl = (ret == 0)

answer = 'YES' if bl else 'NO'
print(answer)

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 2 * a < sum_b or a > sum_b:
        print("NO")
        exit()
    return 2 * a - sum_b

# ？？？？？？
for v, e in enumerate(E[1:], 1):
    if len(e) > 1:
        break
ans = dfs(v)
if (ans==0 and len(E[v])>1) or (ans==A[v] and len(E[v])==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 2 * a < sum_b or a > sum_b:
        print("NO")
        exit()
    return 2 * a - sum_b

# ？？？？？？
for v, e in enumerate(E[1:], 1):
    if len(e) == 1:
        break
ans = dfs(v)
if (ans==0 and len(E[v])>1) or (ans==A[v] and len(E[v])==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 2 * a < 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")