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: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = [0] + list(map(int,readline().split()))
data = list(map(int,read().split()))

links = [[] for _ in range(n+1)]
it = iter(data)
for ai,bi in zip(it,it):
    links[ai].append(bi)
    links[bi].append(ai)

links[0].append(1)
links[1].append(0)

tp = []
parent = [-1] * (n+1)
stack = [0]
while(stack):
    i = stack.pop()
    for j in links[i]:
        if(parent[i]==j):
            continue
        parent[j] = i
        stack.append(j)
        tp.append(j)

tp = tp[::-1]
come = [[] for _ in range(n+1)]

for i in tp:
    if(len(come[i])==0):
        # print(i)
        # print(parent[i])
        # print(a[i])
        # print(come[parent[i]])
        # print('--')
        come[parent[i]].append(a[i])
        continue

    up = 2*a[i] - sum(come[i])
    if(up < 0)|(max(up,max(come[i])) > a[i]):
        print('NO')
        exit()
    come[parent[i]].append(up)

# print(come)

if(len(come[1]) > 1)&(come[0][0] == 0):
    print('YES')
elif(len(come[1]) == 1)&(come[0][0] == a[1]):
    print('YES')
else:
    print('NO')

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc010/tasks/agc010_c

似たような問題を最近やらなかったっけ…？
→Complete Compressか

部分木に注目してみる

部分木から飛び出すパスの個数をXとしてみよう
余ったパスは上に投げるしかない
→部分木から飛び出すパスの本数の最小をYとすると、Y[根] == 0 が答え
根は葉でない頂点を適当に選ぶ

飛び出すパスの本数の最小はどう計算するか？
最大と最小を受け取る
いい感じにつなげて最小と最大を導出したい

まず、最大・最小間はすべて作れるのか？
2本飛び出している奴を接続すると、飛び出しは2減り、1余るので飛び出しが1ふえる…？
→もしかして飛び出し本数の候補はより少ない？

容量が X で、子が全部葉、 a,bとする
n組繋げたとすると、 a+b-2n 本飛び出す
X = n + (a+b-2n) = a+b-n
なので、nは一定値になる n = a+b-X
nは、最小は0、最大は過半数でなければa+b+…　にでき、そうでなければ最大値以外の和の範囲を取れる
nがその条件を満たしているかを調べればいい

"""

from sys import stdin
import sys
sys.setrecursionlimit(200000)

def dfs(v,p):
    if len(lis[v]) == 1:
        return A[v]

    chlis = []
    for nex in lis[v]:
        if nex != p:
            chlis.append(dfs(nex,v))
    chlis.sort()
    chsum = sum(chlis)

    n = chsum - A[v]
    if chlis[-1] * 2 <= chsum:
        if 0 <= n <= chsum//2:
            pass
        else:
            print ("NO")
            sys.exit()
    else:
        if 0 <= n <= chsum-chlis[-1]:
            pass
        else:
            print ("NO")
            sys.exit()
    return chsum - 2 * n

N = int(stdin.readline())

A = list(map(int,stdin.readline().split()))
if N == 2:
    if A[0] == A[1]:
        print ("YES")
    else:
        print ("NO")
    sys.exit()

lis = [ [] for i in range(N)]

for loop in range(N-1):
    u,v = map(int,stdin.readline().split())
    u -= 1
    v -= 1
    lis[u].append(v)
    lis[v].append(u)

root = None
for i in range(N):
    if len(lis[i]) > 1:
        root = i
        break

ret = dfs(root,root)
if ret == 0:
    print ("YES")
else:
    print ("NO")

Submission status: Accepted

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には葉以外を選ぶ
root = -1
for v in range(n):
    if len(tree[v]) != 1:
        root = v
        break
        
# 頂点2つのときはrootを葉として選べない
if root == -1:
    if a[0] == a[1]:
        print("YES")
    else:
        print("NO")
    exit()
    
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 v == root and cnt1 != 0:
        is_YES = False
        break
    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: Accepted

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")
    exit()

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: Accepted

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 or pair > x // 2:
            return False
        dp[v] = x - 2 * pair
    return dp[root] == 0

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

Submission status: Accepted

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: Accepted

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
  if C[v] > A[par] or C[v] > A[v]:
    return False
  C[par] -= C[v]
  return True
if dfs(0):
  print("YES")
else:
  print("NO")

Submission status: Accepted

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
                if p == 0 and kmax-2*(kmax-A[p]) != 0:
                    return False
                need[Parent[p]].append(kmax-2*(kmax-A[p]))
    return True

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

Submission status: Accepted

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
if r == -1:
    assert N==2
    print('YES' if A[0]==A[1] else 'NO')
    exit()

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: Accepted

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[1] == stone[2]:
    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: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, aaa):
    if len(links[v]) == 1:
        return aaa[v]

    children = []
    for u in links[v]:
        if u == p:
            continue
        result = dfs(u, v, aaa)
        if result == -1:
            return -1
        children.append(result)

    if len(children) == 1:
        if aaa[v] != children[0]:
            return -1
        return children[0]

    c_sum = sum(children)
    c_max = max(children)
    o_max = c_sum - c_max

    if o_max >= c_max:
        max_pairs = c_sum // 2
    else:
        max_pairs = o_max
    min_remain = c_sum - max_pairs
    if not min_remain <= aaa[v] <= c_sum:
        return -1

    return aaa[v] * 2 - c_sum


def solve(n, aaa, links):
    if n == 2:
        return aaa[0] == aaa[1]
    # 葉でない頂点探し
    s = 0
    while len(links[s]) == 1:
        s += 1
    return dfs(s, -1, aaa) == 0


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

print('YES' if solve(n, aaa, links) else 'NO')

Submission status: Accepted

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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 not 0 <= x <= 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 <= x <= 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: Accepted

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, jud, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, A, use, Wlist, visit, jud, 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
			jud[node] = "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
	jud = ["YES"] * N
	Wlist = [[] for i in range(N)]
	visit = ["No"] * N
	visit[s] = "Yes"
	DFS(G, A, use, Wlist, visit, jud, s)
	# print(use)

	for i in range(N):
		if jud[i] == "NO":
			judge = "NO"

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

if __name__ == '__main__':
	main()

Submission status: Accepted

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:
            print('NO')
            exit()
        s += ret
    if 2 * x - s > s:
        print('NO')
        exit()
    if 2 * x < s:
        print('NO')
        exit()
    return 2 * x - s


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

if not dfs(v):
    print('YES')
else:
    print('NO')

Submission status: Accepted

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:
            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: Accepted

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

v = 1
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: Accepted

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)
isLeaf = len(chlds[vRoot]) == 1
if (isLeaf and ans == As[vRoot]) or (not isLeaf and ans == 0):
    print('YES')
else:
    print('NO')

Submission status: Accepted

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
    L = sumC - As[vNow]
    if T < 0 or L < 0:
        return -1
    if min(sumC-max(cs), sumC//2) >= L:
        return T
    else:
        return -1

ans = dfs(vRoot)
isLeaf = len(chlds[vRoot]) == 1
if (isLeaf and ans == As[vRoot]) or (not isLeaf and ans == 0):
    print('YES')
else:
    print('NO')

Submission status: Accepted

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 len(af_lis[x]) > 1 and 2*a[x] != s:
				print("NO")
				sys.exit()
			elif len(af_lis[x]) == 1 and a[x] != s:
				print("NO")
				sys.exit()
			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: Accepted

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 0<=S-A[x]<=min(S-max(C),S//2) and 2*A[x]-S>=0:
      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: Accepted

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]] or hen[x]>a[x]:
    print("NO")
    exit()
  if hen[x] <0:
    print("NO")
    exit()
if hen[ne] != a[ne]:
  print("NO")
else:
  print("YES")

Submission status: Accepted

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]
	child_cnt=0
	child_max=-1
	for to in adj[cur]:
		if to!=father:
			result=dfs(to, cur)
			child_cnt+=result
			child_max=max(child_max, result)
	result=value[cur]*2-child_cnt
	if result<0 or result-child_cnt>0 or child_max>child_cnt-child_max+result:
		raise Exception, [value[cur], child_cnt, child_max, result]
	return result
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: Accepted

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

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

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