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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

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


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

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

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

        if not t:
            return ac

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

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

    return 'NO'




print(main())

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
from collections import deque
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: Runtime Error

Solution code:
import sys

input=sys.stdin.readline
sys.setrcursionlimit(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: Runtime Error

Solution code:
import sys

input=sys.stdin.buffer.readline
sys.setrcursionlimit(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: Runtime Error

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

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
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,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

vector<vi> adj;
vll A;
vll dp;
bool ng=false;

void dfs(int v, int p){
    if (ng) return;
    if (v!=0 && adj[v].size()==1){
        dp[v] = A[v];
        return;
    }
    ll sum=0,cnt=0;
    for(auto u:adj[v]){
        if (u==p) continue;
        dfs(u,v);
        sum+=dp[u];
        cnt++;
    }
    if (cnt==1){
        if (sum==A[v]) dp[v]=A[v];
        else{
            ng=true;
            return;
        }
    }
    ll x = sum-A[v];
    if (x<0){ng=true; return;}
    ll y = A[v]-x;
    if (y<0){ng=true; return;}
    dp[v] = y;
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    adj.resize(n);
    A.resize(n);
    dp.resize(n);
    rep(i,n) cin>>A[i];
    rep(i,n-1){
        int a,b; cin>>a>>b; a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(0,-1);
    if (ng){
        cout<<"NO\n";
    }else{
        cout<<"YES\n";
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import random
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:
  print(2/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: Runtime Error

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):
    # 葉でない頂点探し
    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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 5)


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):
    # 葉でない頂点探し
    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: Runtime Error

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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]) - candi[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: Runtime Error

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

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

#部分木 大きさ
import sys
sys.setrecursionlimit(10**7)

from collections import defaultdict

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

	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: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Visited=[False]*N
B=[0]*N
def B_map(x):
  C=[]
  S=-1
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      res=B_map(i)
      if S<0:
        S=res
      else:
        S+=res
      C.append(res)
  if S<0:
    B[x]=A[x]
  else:
    M=max(max(C),sum(C)//2)
    T=2*A[x]-S
    if 0<=(S-T)//2<=M:
      B[x]=2*A[x]-S
    else:
      print("NO")
      exit()
    if x==0 and T!=0:
      print("NO")
      exit()
  return B[x]
B_map(0)
for i in range(N):
  if B[i]<0:
    print("NO")
    exit()
print("YES")

Submission status: Runtime Error

Solution code:
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):
  res=-1
  Visited[x]=True
  for i in G[x]:
    if not Visited[i]:
      if res<0:
        res=B_map(i)
      else:
        res+=B_map(i)
  if res<0:
    B[x]=A[x]
  else:
    B[x]=2*A[x]-res
  return B[x]
B_map(0)
for i in range(N):
  if B[i]<0:
    print("NO")
    exit()
print("YES")

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import copy

def traverse(N,A,mm):
	if N<2 or len(A)!=N+1 or len(mm)!=N+1:
		return(False)
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	c=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
		c.extend([[0]])
	
	start=1
	for i in range(start,N+1):
		if len(m[i])==1 and A[i]>0:
		#if A[i]>0:
			root=i
			break
	
	eerror=False
	if len(m[root]) in [0,1]:
		t[root]=A[root]
	else:
		t[root]=2*A[root]
	
	r=0
	i=root
	while not(i==root and len(m[i])==0):
		#print(i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			#print('back')
			c[i][0]=t[i]
			r=i
			i=rp[i]
			#print(i,t[i],m[i],rp[i])
			t[i]-=t[r]
			c[i].extend([t[r]])
			#print('minus')
			#print(c)
			if t[i]<0:
				return(False)
				#eerror=True
				#break
		else:
			#print('forward')
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
			#print(i,t[i],m[i],rp[i])	
			if len(m[i]) in [0,1]:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
			#print('plus')
			#print(i,t[i],m[i],rp[i])
			if r in m[i]:
				m[i].remove(r)
				#print('remove')
		
	
	for cc in c[1:]:
		cc_max=cc.index(max(cc))
		if len(cc)>2 and cc[cc_max]>sum([cc[i] for i in range(len(cc)) if i!=cc_max]):
			return(False)
			
	if t[root]==0 and eerror==False:
		return(True)
	else:
		return(False)
		
		
N= int(input())
A=[0]
for x in input().split():
	A.extend([int(x)])
	
m=[]

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

for i in range(N-1):
	l=[int(xx) for xx in input().split()]
	#l=[int(xx) for xx in L.pop()]
	if 0<l[0]<=N and 0<l[1]<=N:
		m[l[0]]+=[l[1]]
		m[l[1]]+=[l[0]]

		
if traverse(N,A,m):
	print('YES')
else:
	print('NO')

Submission status: Runtime Error

Solution code:
import copy

def traverse(N,A,mm):
	if N<2 or len(A)!=N+1 or len(mm)!=N+1:
		return(False)
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	c=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
		c.extend([[0]])
	
	start=1
	for i in range(start,N+1):
		#if len(m[i])==1 and A[i]>0:
		if A[i]>0:
			root=i
			break
	
	eerror=False
	if len(m[root]) in [0,1]:
		t[root]=A[root]
	else:
		t[root]=2*A[root]
	
	r=0
	i=root
	while not(i==root and len(m[i])==0):
		#print(i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			#print('back')
			c[i][0]=t[i]
			r=i
			i=rp[i]
			#print(i,t[i],m[i],rp[i])
			t[i]-=t[r]
			c[i].extend([t[r]])
			#print('minus')
			#print(c)
			if t[i]<0:
				return(False)
				#eerror=True
				#break
		else:
			#print('forward')
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
			#print(i,t[i],m[i],rp[i])	
			if len(m[i]) in [0,1]:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
			#print('plus')
			#print(i,t[i],m[i],rp[i])
			if r in m[i]:
				m[i].remove(r)
				#print('remove')
		
	
	for cc in c[1:]:
		cc_max=cc.index(max(cc))
		if len(cc)>2 and cc[cc_max]>sum([cc[i] for i in range(len(cc)) if i!=cc_max]):
			return(False)
			
	if t[root]==0 and eerror==False:
		return(True)
	else:
		return(False)
		
		
N= int(input())
A=[0]
for x in input().split():
	A.extend([int(x)])
	
m=[]

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

for i in range(N-1):
	l=[int(xx) for xx in input().split()]
	#l=[int(xx) for xx in L.pop()]
	if 0<l[0]<=N and 0<l[1]<=N:
		m[l[0]]+=[l[1]]
		m[l[1]]+=[l[0]]

		
if traverse(N,A,m):
	print('YES')
else:
	print('NO')

Submission status: Runtime Error

Solution code:
import copy

def traverse(N,A,mm):
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	c=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
		c.extend([[0]])
	
	start=1
	for i in range(start,N+1):
		#if len(m[i])==1 and A[i]>0:
		if A[i]>0:
			root=i
			break
	
	eerror=False
	if len(m[root]) in [0,1]:
		t[root]=A[root]
	else:
		t[root]=2*A[root]
	
	
	i=root
	while not(i==root and len(m[i])==0):
		#print(i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			#print('back')
			c[i][0]=t[i]
			r=i
			i=rp[i]
			#print(i,t[i],m[i],rp[i])
			t[i]-=t[r]
			c[i].extend([t[r]])
			#print('minus')
			#print(c)
			if t[i]<0:
				return(False)
				#eerror=True
				#break
		else:
			#print('forward')
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
			#print(i,t[i],m[i],rp[i])	
			if len(m[i]) in [0,1]:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
			#print('plus')
			#print(i,t[i],m[i],rp[i])
			if r in m[i]:
				m[i].remove(r)
				#print('remove')
		
	
	for cc in c[1:]:
		cc_max=cc.index(max(cc))
		if len(cc)>2 and cc[cc_max]>sum([cc[i] for i in range(len(cc)) if i!=cc_max]):
			return(False)
			
	if t[root]==0 and eerror==False:
		return(True)
	else:
		return(False)
		
		
N= int(input())
A=[0]
for x in input().split():
	A.extend([int(x)])

m=[]

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

for i in range(N-1):
	l=[int(xx) for xx in input().split()]
	#l=[int(xx) for xx in L.pop()]
	if 0<l[0]<=N and 0<l[1]<=N:
		m[l[0]]+=[l[1]]
		m[l[1]]+=[l[0]]

		
if traverse(N,A,m):
	print('YES')
else:
	print('NO')

Submission status: Runtime Error

Solution code:
import copy

def traverse(N,A,mm):
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	c=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
		c.extend([[0]])
	
	start=1
	for i in range(start,N+1):
		#if len(m[i])==1 and A[i]>0:
		if A[i]>0:
			root=i
			break
	
	eerror=False
	if len(m[root]) in [0,1]:
		t[root]=A[root]
	else:
		t[root]=2*A[root]
	
	
	while not(i==root and len(m[i])==0):
		#print(i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			#print('back')
			c[i][0]=t[i]
			r=i
			i=rp[i]
			#print(i,t[i],m[i],rp[i])
			t[i]-=t[r]
			c[i].extend([t[r]])
			#print('minus')
			#print(c)
			if t[i]<0:
				return(False)
				#eerror=True
				#break
		else:
			#print('forward')
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
			#print(i,t[i],m[i],rp[i])	
			if len(m[i]) in [0,1]:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
			#print('plus')
			#print(i,t[i],m[i],rp[i])
			if r in m[i]:
				m[i].remove(r)
				#print('remove')
		
	
	for cc in c[1:]:
		cc_max=cc.index(max(cc))
		if len(cc)>2 and cc[cc_max]>sum([cc[i] for i in range(len(cc)) if i!=cc_max]):
			return(False)
			
	if t[root]==0 and eerror==False:
		return(True)
	else:
		return(False)
		
		
N= int(input())
A=[0]
for x in input().split():
	A.extend([int(x)])

m=[]

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

for i in range(N-1):
	l=[int(xx) for xx in input().split()]
	#l=[int(xx) for xx in L.pop()]
	if 0<l[0]<=N and 0<l[1]<=N:
		m[l[0]]+=[l[1]]
		m[l[1]]+=[l[0]]

		
if traverse(N,A,m):
	print('YES')
else:
	print('NO')

Submission status: Runtime Error

Solution code:
import copy

def traverse(N,A,mm):
	m=copy.deepcopy(mm)
	t=[]
	rp=[]
	c=[]
	for i in range(N+1):
		t.extend([0])
		rp.extend([0])
		c.extend([[0]])
	
	start=1
	for i in range(start,N+1):
		#if len(m[i])==1 and A[i]>0:
		if A[i]>0:
			root=i
			break
	
	eerror=False
	if len(m[root]) in [0,1]:
		t[root]=A[root]
	else:
		t[root]=2*A[root]
	
	
	while not(i==root and len(m[i])==0):
		#print(i,t[i],m[i],rp[i])
		
		if len(m[i])==0:
			#print('back')
			c[i][0]=t[i]
			r=i
			i=rp[i]
			#print(i,t[i],m[i],rp[i])
			t[i]-=t[r]
			c[i].extend([t[r]])
			#print('minus')
			#print(c)
			if t[i]<0:
				eerror=True
				break
		else:
			#print('forward')
			r=i
			i=m[i].pop()
			if rp[i]==0:
				rp[i]=r
			#print(i,t[i],m[i],rp[i])	
			if len(m[i]) in [0,1]:
				t[i]=A[i]
			else:
				t[i]=2*A[i]
			#print('plus')
			#print(i,t[i],m[i],rp[i])
			if r in m[i]:
				m[i].remove(r)
				#print('remove')
		
	
	for cc in c[1:]:
		cc_max=cc.index(max(cc))
		if len(cc)>2 and cc[cc_max]>sum([cc[i] for i in range(len(cc)) if i!=cc_max]):
			return(False)
			
	if t[root]==0 and eerror==False:
		return(True)
	else:
		return(False)
		
		
N= int(input())
A=[0]
for x in input().split():
	A.extend([int(x)])

m=[]

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

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

		
if traverse(N,A,m):
	print('YES')
else:
	print('NO')