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:
def get_par(tree: list, root: int) -> list:
    """根付き木の頂点それぞれの親を求める"""
    n = len(tree)
    visited = [False] * n
    visited[root] = True
    par = [-1] * n
    stack = [root]
    while stack:
        v = stack.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            stack.append(nxt_v)
            par[nxt_v] = v
    return par


def topological_sort(tree: list, root) -> list:
    """根付き木をトポロジカルソートする"""
    n = len(tree)
    visited = [False] * n
    visited[root] = True
    tp_sorted = [root]
    stack = [root]
    while stack:
        v = stack.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v]:
                continue
            visited[nxt_v] = True
            stack.append(nxt_v)
            tp_sorted.append(nxt_v)
    return tp_sorted


n = int(input())
a = list(map(int, input().split()))
edges = [list(map(int, input().split())) for i in range(n - 1)]


tree = [[] for i in range(n)]
for u, v in edges:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

root = 0
par = get_par(tree, root)
tp_sorted = topological_sort(tree, root)

stn_cnt = [[] for _ in range(n)]

# 葉から探索
is_YES = True
for v in tp_sorted[::-1]:
    if not stn_cnt[v]:
        par_v = par[v]
        stn_cnt[par_v].append(a[v])
        continue
    sum_cnt = sum(stn_cnt[v])
    max_cnt = max(stn_cnt[v])
    if sum_cnt < a[v]:
        is_YES = False
        break
    cnt1 = 2 * a[v] - sum_cnt
    cnt2 = sum_cnt - a[v]
    if cnt1 < 0:
        is_YES = False
        break
    if cnt2 < 0 or min(sum_cnt - max_cnt, sum_cnt // 2) < cnt2:
        is_YES = False
        break
    par_v = par[v]
    stn_cnt[par_v].append(cnt1)

if is_YES:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

for _ in range(n-1):
    aa, b = map(int, input().split())
    aa -= 1
    b -= 1
    g[aa].append(b)
    g[b].append(aa)
    if len(g[aa]) == 2:
        root = aa
    if len(g[b]) == 2:
        root = b

visited = [False]*n


def dfs(v):
    visited[v] = True
    chl = []
    for w in g[v]:
        if not visited[w]:
            ret = dfs(w)
            chl.append(ret)
    if len(chl) == 0:
        return a[v]
    ret = 2*a[v]-sum(chl)
    res = sum(chl)-a[v]
    if res < 0 or (v == root and ret != 0) or (len(chl) == 1 and res != 0):
        print('NO')
        exit()
    chl = sorted(chl)
    l = 0
    r = len(chl) - 1
    while res > 0:
        if chl[l] == 0:
            l += 1
        if chl[r] == 0:
            r -= 1
        if l != r:
            chl[l] -= 1
            chl[r] -= 1
            res -= 1
        else:
            print('NO')
            exit()
    return ret


dfs(root)
print('YES')

Submission status: Wrong Answer

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

n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

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

for _ in range(n-1):
    aa, b = map(int, input().split())
    aa -= 1
    b -= 1
    g[aa].append(b)
    g[b].append(aa)
    if len(g[aa]) == 2:
        root = aa
    if len(g[b]) == 2:
        root = b

visited = [False]*n


def dfs(v):
    visited[v] = True
    chl = []
    for w in g[v]:
        if not visited[w]:
            ret = dfs(w)
            chl.append(ret)
    if len(chl) == 0:
        return a[v]
    elif len(chl) == 1:
        if a[v] == chl[0]:
            return a[v]
        else:
            print('NO')
            exit()
    ret = 2*a[v]-sum(chl)
    res = sum(chl)-a[v]
    if res < 0 or (v == root and ret != 0):
        print('NO')
        exit()
    chl = sorted(chl)
    l = 0
    r = len(chl) - 1
    while res > 0:
        if chl[l] == 0:
            l += 1
        if chl[r] == 0:
            r -= 1
        if l != r:
            chl[l] -= 1
            chl[r] -= 1
            res -= 1
        else:
            print('NO')
            exit()
    return ret


dfs(root)
print('YES')

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.buffer.readline
sys.setrecursionlimit(2*10**5)

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

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

root=0
for i in range(N):
    if len(edge[i])!=1:
        root=i
        break

def cond(L,n):
    check=0
    for i in L:
        check+=min(n,i)
    return check>=2*n

def dfs(v,pv):
    s=A[v]
    t=[]
    for nv in edge[v]:
        if nv!=pv:
            y=dfs(nv,v)
            t.append(y)
    #2*a+b=t
    #a+b=s
    T=sum(t)
    if T==0:
        if len(edge[v])==1:
            return s

    start=0
    end=T//2
    while end-start>1:
        test=(end+start)//2
        if cond(t,test):
            start=test
        else:
            end=test
    if cond(t,end):
        M=end
    else:
        M=start

    a=T-s
    b=2*s-T
    if 0>a or 0>b:
        print("NO")
        exit()
    elif a>M:
        print("NO")
        exit()
    return b

res=dfs(root,-1)
print("YES" if res==0 else "NO")

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.buffer.readline
sys.setrecursionlimit(2*10**5)

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

root=0
for i in range(N):
    if len(edge[i])!=1:
        root=i
        break

def cond(L,n):
    check=0
    for i in L:
        check+=min(n,i)
    return check>=2*n

def dfs(v,pv):
    s=A[v]
    t=[]
    for nv in edge[v]:
        if nv!=pv:
            y=dfs(nv,v)
            t.append(y)
    #2*a+b=t
    #a+b=s
    T=sum(t)
    if T==0:
        if len(edge[v])==1:
            return s

    start=0
    end=T//2
    while end-start>1:
        test=(end+start)//2
        if cond(t,test):
            start=test
        else:
            end=test
    if cond(t,end):
        M=end
    else:
        M=start

    a=T-s
    b=2*s-T
    if 0>a or 0>b:
        print("NO")
        exit()
    elif a>M:
        print("NO")
        exit()
    return b

res=dfs(root,-1)
print("YES" if res==0 else "NO")

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.buffer.readline
sys.setrecursionlimit(2*10**5)

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

root=0
for i in range(N):
    if len(edge[i])!=1:
        root=i
        break

def dfs(v,pv):
    s=A[v]
    t=0
    for nv in edge[v]:
        if nv!=pv:
            y=dfs(nv,v)
            t+=y
    #2*a+b=t
    #a+b=s
    if t==0:
        if len(edge[v])==1:
            return s
    a=t-s
    b=2*s-t
    if 0>a or 0>b:
        print("NO")
        exit()
    return b

res=dfs(root,-1)
print("YES" if res==0 else "NO")

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = (0, ) + tuple(map(int, readline().split()))
m = map(int, read().split())
G = [[] for _ in range(N + 1)]
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

def dfs_order(G, root=1):
    parent = [0] * (N + 1)
    order = []
    stack = [root]
    while stack:
        x = stack.pop()
        order.append(x)
        for y in G[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
    return parent, order

def main(N, A, G):
    if N == 2:
        return A[1] == A[2]
    degree = [len(x) for x in G]
    root = degree.index(max(degree))
    parent, order = dfs_order(G, root)
    # 上に伸ばすパスの個数
    dp = [0] * (N + 1)
    for v in order[::-1]:
        if degree[v] == 1:
            dp[v] = A[v]
            continue
        p = parent[v]
        nums = [dp[w] for w in G[v] if v != p]
        x = sum(nums)
        y = max(nums)
        pair = x - A[v]
        if pair < 0 or pair > x - y:
            return False
        dp[v] = x - 2 * pair
    return dp[root] == 0

print('YES' if main(N, A, G) else 'NO')

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.buffer.readline
sys.setrecursionlimit(2*10**5)

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

root=0
for i in range(N):
    if len(edge[i])!=1:
        root=i
        break

def dfs(v,pv):
    s=A[v]
    t=0
    for nv in edge[v]:
        if nv!=pv:
            y=dfs(nv,v)
            t+=y
    #2*a+b=t
    #a+b=s
    if t==0:
        if len(edge[v])!=1:
            print("NO")
            exit()
        else:
            return s
    a=t-s
    b=2*s-t
    if 0>a or 0>b:
        print("NO")
        exit()
    return b

res=dfs(root,-1)
print("YES" if res==0 else "NO")

Submission status: Wrong Answer

Solution code:
print("YES")

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.buffer.readline
sys.setrecursionlimit(2*10**5)

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

root=0
for i in range(N):
    if len(edge[i])!=1:
        root=i
        break

def dfs(v,pv):
    s=A[v]
    t=0
    for nv in edge[v]:
        if nv!=pv:
            y=dfs(nv,v)
            t+=y
    #2*a+b=t
    #a+b=s
    if t==0:
        if len(edge[v])!=1:
            print("NO")
            exit()
        else:
            return s
    a=t-s
    b=2*s-t
    if 2*a>t:
        print("NO")
        exit()
    return b

res=dfs(root,-1)
print("YES" if res==0 else "NO")

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    if s==-1:
        if A[0]==A[1]:
            print("YES")
        else:
            print("NO")
        return
    def dfs(s,p):
        flag = 1
        rep = 0
        maxA = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s)
            if maxA<cur:
                maxA = cur
            rep += cur
            flag *= next
        if len(V[s])==1:
            return A[s],flag
        if (rep+1)//2>A[s] or rep<A[s] or maxA<A[s]:
            flag = 0
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1)
    if rep!=0:
        flag = 0
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    if s==-1:
        if A[0]==A[1]:
            print("YES")
        else:
            print("NO")
        return
    def dfs(s,p):
        flag = 1
        rep = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s)
            rep += cur
            flag *= next
        if len(V[s])==1:
            return A[s],flag
        if (rep+1)//2>A[s] or rep<A[s]:
            flag = 0
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1)
    if rep!=0:
        flag = 0
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    def dfs(s,p):
        flag = 1
        rep = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s)
            rep += cur
            flag *= next
        if len(V[s])==1:
            return A[s],flag
        if (rep+1)//2>A[s] or rep<A[s]:
            flag = 0
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1)
    if rep!=0:
        flag = 0
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    def dfs(s,p):
        flag = 1
        rep = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s)
            rep += cur
            flag *= next
        if len(V[s])==1:
            rep = A[s]
            if rep==0:
                return 0,flag
        if (rep+1)//2>A[s] or rep<A[s]:
            flag = 0
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1)
    if rep!=0:
        flag = 0
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    def dfs(s,p):
        flag = 1
        rep = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s)
            rep += cur
            flag *= next
        if len(V[s])==1:
            rep = A[s]
        if (rep+1)//2>A[s] or rep<A[s]:
            flag = 0
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1)
    if rep!=0:
        flag = 0
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    flag = True
    def dfs(s,p,flag):
        rep = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s,flag)
            rep += cur
            flag *= next
        if len(V[s])==1:
            rep = A[s]
        if (rep+1)//2>A[s] or rep<A[s]:
            flag = False
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1,flag)
    if rep!=0:
        flag = False
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    flag = True
    def dfs(s,p,flag):
        rep = 0
        for v in V[s]:
            if v==p:
                continue
            rep += dfs(v,s,flag)[0]
        if len(V[s])==1:
            rep = A[s]
        if (rep+1)//2>A[s] or rep<A[s]:
            flag = False
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1,flag)
    if rep!=0:
        flag = False
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

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 if len(T[i]) == 1 else a*2 for i, a in enumerate(A)]
D = tuple(c for c in C)
def dfs(v, par=-1):
  for nv in T[v]:
    if nv != par:
      if not dfs(nv, v):
        return False
  if C[v] < 0:
    return False
  if par == -1:
    return C[v] == 0
  if len(T[par]) > 1 and C[v] > D[par]//2:
    return False
  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
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 if len(T[i]) == 1 else a*2 for i, a in enumerate(A)]
D = tuple(c for c in C)
def dfs(v, par=-1):
  for nv in T[v]:
    if nv != par:
      if not dfs(nv, v):
        return False
  if C[v] < 0:
    return False
  if par == -1:
    return C[v] == 0
  if C[v] > D[par]//2:
    return False
  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
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 if len(T[i]) == 1 else a*2 for i, a in enumerate(A)]
D = tuple(c for c in C)
def dfs(v, par=-1):
  for nv in T[v]:
    if nv != par:
      if not dfs(nv, v):
        return False
  if C[v] < 0:
    return False
  if par == -1:
    return C[v] == 0
  if C[v] > D[par]:
    return False
  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
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 if len(T[i]) == 1 else a*2 for i, a in enumerate(A)]
def dfs(v, par=-1):
  global C
  for nv in T[v]:
    if nv != par:
      if not dfs(nv, v):
        return False
  if C[v] < 0:
    return False
  if par == -1:
    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
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 if len(T[i]) == 1 else a*2 for i, a in enumerate(A)]
def dfs(v, par=-1):
  for nv in T[v]:
    if nv != par:
      if not dfs(nv, v):
        return False
  if C[v] < 0:
    return False
  if par == -1:
    return C[v] == 0
  C[par] -= C[v]
  return True
if dfs(0):
  print("YES")
else:
  print("NO")