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

Solution (Python):
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())

Solution (Python):
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])
        
        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"

Solution (Python):



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)

Solution (Python):
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()