Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > a_{u}, where a_{u} is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?


-----Input-----

In the first line of the input integer n (1 ≤ n ≤ 10^5) is given — the number of vertices in the tree.

In the second line the sequence of n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) is given, where a_{i} is the number written on vertex i.

The next n - 1 lines describe tree edges: i^{th} of them consists of two integers p_{i} and c_{i} (1 ≤ p_{i} ≤ n,  - 10^9 ≤ c_{i} ≤ 10^9), meaning that there is an edge connecting vertices i + 1 and p_{i} with number c_{i} written on it.


-----Output-----

Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.


-----Example-----
Input
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

Output
5



-----Note-----

The following image represents possible process of removing leaves from the tree:  [Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())

A = list(map(int, input().split()))

maxDist = [0] * n

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

for v in range(1, n):
    u, d = tuple(map(int, input().split()))
    u -= 1
    G[v].append((u, d))
    G[u].append((v, d))


seen = [False] * n
seen[0] = True
q = [0]
to_remove = []

while q:
    v = q.pop();
    for u, dist in G[v]:
        if not seen[u]:
            seen[u] = True
            maxDist[u] = max(dist, maxDist[v] + dist)
            if maxDist[u] > A[u]:
                to_remove.append(u)
            else:
                q.append(u)

count = 0
while to_remove:
    v = to_remove.pop()
    count += 1
    for u, _ in G[v]:
        if not seen[u]:
            seen[u] = True
            to_remove.append(u)

print(count)

import sys

def main():
    u = []
    r = 0
    x = []
    q = []


    n = int(sys.stdin.readline())
    x = list(map(int, sys.stdin.readline().split()))
    links = [[] for i in range(n)]
    u = [False]*n
    p = [0]*n
    d = [False]*n

    data = sys.stdin.readlines()
    for i in range(n-1):
        y = data[i].split()    
        v , c = int(y[0])-1, int(y[1])
        links[i+1].append((v,c))
        links[v].append((i+1,c))

    u[0] = True
    q.append((0,0,False))
    while len(q)!=0:
        z = q.pop()
        i, path, al = z[0], z[1],z[2]
        for y in links[i]:
            j , c = y[0], y[1]
            if not u[j] :
                u[j] = True
                #print("dfs", j, path, c)
                al2 = al
                np = max(path + c, c)
                if np>x[j]:
                    al2 = True
                if al2:
                    r+=1
                #print(j , np , x[j], al2)
                q.append((j, np, al2)) 

    print(r)


main()


n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for u in range(1, n):
    p, c = (int(x) for x in input().split())
    g[p-1].append((u, c))

stack = [(0, 0, False)]
r = 0
while stack:
    u, d, f = stack.pop()
    f = f or d > a[u]
    if f:
        r += 1
    for v, c in g[u]:
        stack.append((v, d + c if d + c >= 0 else 0, f))

print(r)

from queue import deque
#sys.setrecursionlimit(10**6)

n = int(input())
a = [0] + list(map(int, input().split()))

G = {i : [] for i in range(1, n+1)}

for i in range(1, n):
    parent, edge = list(map(int, input().split()))
    G[parent].append((i + 1, edge))

cut = 0
stack = [(1, 0, False)]

while stack:
    v, cur_max, to_cut = stack.pop()

    if cur_max > a[v] and not to_cut:
        to_cut = True
        cut += 1

    if to_cut:
        cut += len(G[v])

    for u, e in G[v]:
        stack.append((u, max(0, cur_max + e), to_cut))

print(cut)





"""
	Author		: Arif Ahmad
	Date  		: 18-06-16
	Algo  		: DFS
	Difficulty	: Medium
"""

def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	
	g = [[] for x in range(n+1)]
	cost = {}
	for i in range(2, n+1):
		p, c = list(map(int, input().split()))
		g[p].append((i, c))

	stack = [(1, 0, False)]
	ans = 0
	while stack:
		u, dist, sad = stack.pop()
		sad = sad or dist > a[u]
		if sad: ans += 1
		for v, c in g[u]:
			stack.append((v, max(0, dist+c), sad))

	print(ans)


def __starting_point():
    main()
    

__starting_point()

from sys import *
setrecursionlimit(1000001)
n=int(input())
a=[0]+list(map(int,input().split()))
E=[[] for _ in range(n+1)]
k=[1]*(n+1)
for i in range(n-1):
    p,c=map(int,input().split())
    E[i+2]+=[(p,c)]
    E[p]+=[(i+2,c)]
def bfs(nom,pre=0):
    ch,ii=[(nom,pre)],0
    while ii<len(ch):
        nom,pre=ch[ii]
        for x,c in E[nom]:
            if x!=pre: ch+=[(x,nom)]
        ii+=1
    for i in range(len(ch)-1,-1,-1):
        nom,pre=ch[i]
        for x,c in E[nom]:
            if x!=pre: k[nom]+=k[x]        
    
bfs(1)
def bfs2(nom,pre=0,l=0):
    ch=[(nom,pre,l)]
    ans=0
    while ch!=[]:
        nom,pre,l=ch.pop()
        if l>a[nom]: ans+=k[nom]; continue
        for x,c in E[nom]:
            if x!=pre:  
                ch+=[(x,nom,max(l+c,c))]
    return ans
print(bfs2(1))

n=int(input())
a=[0]+list(map(int,input().split()))
E=[[] for _ in range(n+1)]
for i in range(n-1):
    p,c=map(int,input().split())
    E[i+2]+=[(p,c)]
    E[p]+=[(i+2,c)]

ans=0
ch=[(1,0,0)]
while ch:
    nom,pre,l=ch.pop()
    if l>a[nom]: continue
    ans+=1
    for x,c in E[nom]:
        if x!=pre: ch+=[(x,nom,max(l+c,c))]
print(n-ans)

n=int(input())
a=[0]+list(map(int,input().split()))
E=[[] for _ in range(n+1)]
for i in range(n-1):
    p,c=map(int,input().split())
    E[i+2]+=[(p,c)]
    E[p]+=[(i+2,c)]

ans=0
ch=[(1,0,0)]
while ch:
    nom,pre,l=ch.pop()
    if l>a[nom]: continue
    ans+=1
    for x,c in E[nom]:
        t=l+c if l>0 else c
        if x!=pre: ch+=[(x,nom,t)]
print(n-ans)

read = lambda: list(map(int, input().split()))
n = int(input())
a = [0] + list(read())
g = [list() for i in range(n + 1)]
for i in range(2, n + 1):
    p, c = read()
    g[i].append((p, c))
    g[p].append((i, c))
was = [0] * (n + 1)
st = [(1, 0, 0)]
while st:
    v, mind, dist = st.pop()
    was[v] = 1
    for u, c in g[v]:
        if not was[u]:
            if dist + c - min(dist + c, mind) <= a[u]:
                st.append((u, min(mind, dist + c), dist + c))

ans = n - was.count(1)
print(ans)


import sys


def subtree_count():
    stack = [0]
    while len(stack):
        v = stack[-1]

        size = 1
        for u, _ in edge[v]:
            if u in subtree:
                size += subtree[u]
            else:
                stack.append(u)

        if stack[-1] == v:
            stack.pop()
            subtree[v] = size


def remove_bfs():
    queue = [(0, 0)]

    removed = 0

    while len(queue):
        v, s = queue.pop()

        if s > vertex[v]:
            removed += subtree[v]
        else:
            for u, c in edge[v]:
                queue.append((u, max(s + c, 0)))

    return removed

sys.setrecursionlimit(1000001)
n = int(input())

vertex = list(map(int, input().split()))
edge = {}
subtree = {}

for i in range(n):
    edge[i] = []

for i in range(n - 1):
    p, c = list(map(int, input().split()))
    edge[p - 1] += [(i + 1, c)]

subtree_count()
print(remove_bfs())


def subtree_count():
    stack = [0]
    while len(stack):
        v = stack[-1]

        size = 1
        for u, _ in edge[v]:
            if u in subtree:
                size += subtree[u]
            else:
                stack.append(u)

        if stack[-1] is v:
            stack.pop()
            subtree[v] = size


def remove_bfs():
    queue = [(0, 0)]
    removed = 0

    while len(queue):
        v, s = queue.pop()

        if s > vertex[v]:
            removed += subtree[v]
        else:
            for u, c in edge[v]:
                queue.append((u, max(s + c, 0)))

    return removed

n = int(input())

vertex = list(map(int, input().split()))
edge = {}
subtree = {}

for i in range(n):
    edge[i] = []

for i in range(n - 1):
    p, c = list(map(int, input().split()))
    edge.get(p - 1, []).append((i + 1, c))

subtree_count()
print(remove_bfs())


def subtree_count():
    stack = [0]
    while len(stack):
        v = stack[-1]

        size = 1
        for u, _ in edge[v]:
            if u in subtree:
                size += subtree[u]
            else:
                stack.append(u)

        if stack[-1] is v:
            stack.pop()
            subtree[v] = size


def remove_bfs():
    queue = [(0, 0)]
    removed = 0

    while len(queue):
        v, s = queue.pop()

        if s > vertex[v]:
            removed += subtree[v]
        else:
            for u, c in edge[v]:
                queue.append((u, max(s + c, 0)))

    return removed

n = int(input())

vertex = list(map(int, input().split()))
edge = {}
subtree = {}

for i in range(n):
    edge[i] = []

for i in range(n - 1):
    p, c = list(map(int, input().split()))
    edge[p - 1].append((i + 1, c))

subtree_count()
print(remove_bfs())


nn=int(input())
a=[0]+list(map(int,input().split()))
E=[[] for _ in range(nn+1)]
for i in range(nn-1):
    p,c=list(map(int,input().split()))
    E[i+2]+=[(p,c)]
    E[p]+=[(i+2,c)]

ans=0
ch=[(1,0,0)]
while ch:
    nom,pre,l=ch.pop()
    if l>a[nom]: continue
    ans+=1
    for x,c in E[nom]:
        if x!=pre: ch+=[(x,nom,max(l+c,c))]
print(nn-ans)


n=input()
n=int(n)
a=input()
a=a.split()
a[0:0]=[0]
for i in range(1,n+1):
    a[i]=int(a[i])
e=[[]for i in range(0,n+1)]
for i in range(2,n+1):
    x=input()
    x=x.split()
    e[i].append([int(x[0]),int(x[1])])
    e[int(x[0])].append([i,int(x[1])])
q=[1]
cnt=0
f=[0 for i in range(0,n+1)]
dp=[0 for i in range(0,n+1)]
ans=1
while cnt<len(q):
    #print(cnt,len(q))
    now=q[cnt]
    cnt+=1
    for x in e[now]:
        if x[0]!=f[now]:
            f[x[0]]=now
            dp[x[0]]=max(x[1]+dp[now],0)
            if dp[x[0]]>a[x[0]]:
                continue
            q.append(x[0])
            ans+=1
print(n-ans)

from collections import deque
import sys


def bfs(n, adjList, a):
    q = deque()
    dist = [0] * (n+3)
    vis = [False] * (n+3)

    q.append(1)
    vis[1] = True
    cnt = 0

    while q:
        u = q.popleft()

        if a[u] < dist[u]:
            continue

        cnt += 1
        for (v, c) in adjList[u]:
            if not vis[v]:
                vis[v] = True
                dist[v] = max(dist[u]+c, 0)
                q.append(v)

    return cnt


def main():
    # sys.stdin = open("in.txt", "r")

    it = iter(map(int, sys.stdin.read().split()))

    n = next(it)

    a = [0] * (n+3)
    adjList = [[] for _ in range(n+3)]

    for i in range(1, n+1):
        a[i] = next(it)

    for i in range(1, n):
        p = next(it)
        c = next(it)
        adjList[i+1].append((p, c))
        adjList[p].append((i+1, c))

    ans = n - bfs(n, adjList, a)

    sys.stdout.write(str(ans) + '\n')


def __starting_point():
    main()


__starting_point()

from collections import deque
import sys


def bfs(n, adjList, a):
    q = deque()
    dist = [0] * (n+3)
    vis = [False] * (n+3)

    q.append(1)
    vis[1] = True
    cnt = 0

    while q:
        u = q.popleft()

        if a[u] < dist[u]:
            continue

        cnt += 1
        for (v, c) in adjList[u]:
            if not vis[v]:
                vis[v] = True
                dist[v] = max(dist[u]+c, 0)
                q.append(v)

    return cnt


def main():
    # sys.stdin = open("in.txt", "r")

    it = iter(map(int, sys.stdin.read().split()))

    n = next(it)

    a = [0] * (n+3)
    adjList = [[] for _ in range(n+3)]

    for i in range(1, n+1):
        a[i] = next(it)

    for i in range(1, n):
        p = next(it)
        c = next(it)
        adjList[i+1].append((p, c))
        adjList[p].append((i+1, c))

    ans = n - bfs(n, adjList, a)

    sys.stdout.write(str(ans) + '\n')


def __starting_point():
    main()


__starting_point()

from collections import deque
import sys


def bfs(n, adjList, a):
    q = deque()
    dist = [0] * (n+3)
    vis = [False] * (n+3)

    q.append(1)
    vis[1] = True
    cnt = 0

    while q:
        u = q.popleft()

        if a[u] < dist[u]:
            continue

        cnt += 1
        for (v, c) in adjList[u]:
            if not vis[v]:
                vis[v] = True
                dist[v] = max(dist[u]+c, 0)
                q.append(v)

    return cnt


def main():
    # sys.stdin = open("in.txt", "r")

    it = iter(map(int, sys.stdin.read().split()))

    n = next(it)

    a = [0] * (n+3)
    adjList = [[] for _ in range(n+3)]

    for i in range(1, n+1):
        a[i] = next(it)

    for i in range(1, n):
        p = next(it)
        c = next(it)
        adjList[i+1].append((p, c))
        adjList[p].append((i+1, c))

    ans = n - bfs(n, adjList, a)

    sys.stdout.write(str(ans) + '\n')


def __starting_point():
    main()

__starting_point()

n = int(input())
ver = list(map(int, input().split()))
adj = [{} for i in range(n)]

for i in range(n - 1):
    p, c = map(int, input().split())
    adj[i + 1][p - 1] = c
    adj[p - 1][i + 1] = c

from collections import deque
q = deque([(0, 0, 0)])

sad = [0] * n
vis = [0] * n

while q:
    v, d, md = q.popleft()
    vis[v] = 1

    for nv, nvd in adj[v].items():
        if vis[nv] == 1 and sad[nv] == 1:
            sad[v] = 1

    if d > ver[v] or d - md > ver[v]:
        sad[v] = 1

    for nv, nvd in adj[v].items():
        if vis[nv] == 0:
            q.append((nv, d + nvd, min(d + nvd, md)))
    
print(sum(sad))


read = lambda: map(int, input().split())
n = int(input())
a = [0] + list(read())
g = [list() for i in range(n + 1)]
for i in range(2, n + 1):
    p, c = read()
    g[i].append((p, c))
    g[p].append((i, c))
was = [0] * (n + 1)
st = [(1, 0, 0)]
while st:
    v, mind, dist = st.pop()
    was[v] = 1
    for u, c in g[v]:
        if not was[u]:
            if dist + c - min(dist + c, mind) <= a[u]:
                st.append((u, min(mind, dist + c), dist + c))

ans = n - was.count(1)
print(ans)

nn=int(input())

a=[0]+list(map(int,input().split()))

E=[[] for _ in range(nn+1)]

for i in range(nn-1):

    p,c=list(map(int,input().split()))

    E[i+2]+=[(p,c)]

    E[p]+=[(i+2,c)]



ans=0

ch=[(1,0,0)]

while ch:

    nom,pre,l=ch.pop()

    if l>a[nom]: continue

    ans+=1

    for x,c in E[nom]:

        if x!=pre: ch+=[(x,nom,max(l+c,c))]

print(nn-ans)





# Made By Mostafa_Khaled


n = int(input())
a = list(map(int, input().split()))
e = []
for i in range(n):
    e.append([])
for i in range(1, n):
    x, y = map(int, input().split())
    e[x-1].append([i, y])

b = [0] * n
c = [0] * n
d = [(10**18)] * n
l = 0
r = 1
cnt = 0
while l < r:
    v = b[l]
    if c[l] - a[v] > d[l]:
        l += 1
        continue
    cnt += 1
    for x in e[v]:
        c[r] = c[l] + x[1]
        d[r] = min(d[l], c[l])
        b[r] = x[0]
        r += 1
    l += 1
print(n-cnt)

import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):
	"""docstring for Graph"""
	def __init__(self,n,d): # Number of nodes and d is True if directed
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d
		
	def addEdge(self,x,y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root): # NORMAL BFS
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1
					dist[i] = dist[element] + w[(element,i)]


	def bfs2(self, root): # NORMAL BFS
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1
					minn[i] = min(minn[element], dist[i])

	def bfs3(self, root): # NORMAL BFS
		queue = [root]
		queue = deque(queue)
		vis = [0]*self.n
		count = 0
		while len(queue)!=0:
			element = queue.popleft()
			vis[element] = 1
			count += 1
			for i in self.graph[element]:
				if vis[i]==0 and remove[i]==0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1
		return count

	def dfs(self, root, ans): # Iterative DFS
		stack=[root]
		vis=[0]*self.n
		stack2=[]
		while len(stack)!=0: # INITIAL TRAVERSAL
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i]==0:
					self.parent[i] = element
					stack.append(i)

		while len(stack2)!=0: # BACKTRACING. Modify the loop according to the question
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i!=self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest): # Calculate Shortest Path between two nodes
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]]!=-1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0]*self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i]==0:
				q.append(i)
		while len(q)!=0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i]==0:
					q.append(i)
		if vis!=self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0]*n
		while len(stack)!=0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				# Reverse_The_Change()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e]==-1:
				continue
			# Change_The_Answers()

n = int(input())
a = list(map(int,input().split()))
g = Graph(n,False)
w = {}
for i in range(n-1):
	x,y = map(int,input().split())
	w[(i+1,x-1)] = y
	w[(x-1,i+1)] = y
	g.addEdge(i+1,x-1)
dist = [0]*n
minn = [0]*n
g.bfs(0)
g.bfs2(0)
remove = [0]*n
for i in range(1,n):
	if dist[i]-minn[i]>a[i]:
		remove[i] = 1
# print (dist)
# print (minn)
# print (remove)
print (n-g.bfs3(0))

n = int(input())
a = [0] + list(map(int, input().split()))
g = [list() for i in range(n+1)]
for i in range(2, n+1):
    u, v = map(int, input().split())
    g[i].append((u, v))
    g[u].append((i, v))
vis = [0] * (n+1)
stk = [(1, 0, 0)]
while stk:
    v, min_d, dist = stk.pop()
    vis[v] = 1
    for u, c in g[v]:
        if not vis[u]:
            if dist + c - min(min_d, dist+c) <= a[u]:
                stk.append((u, min(min_d, dist+c), dist+c))
print(n - vis.count(1))