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: MEDIUM_HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Dynamic programming
Skill types: Dynamic programming

Starter code:

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


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
				al2 = al
				np = max(path + c, c)
				if np > x[j]:
					al2 = True
				if al2:
					r += 1
				q.append((j, np, al2))
	print(r)
main()


from sys import stdin
n = int(input())
val = [None] + list(map(int, input().split()))
L = stdin.read().splitlines()
tree = [None] * (n + 1)
for i in range(1, n + 1):
	tree[i] = []
for (i, k) in enumerate(L):
	(p, c) = map(int, k.split())
	tree[p].append((i + 2, c))
val[1] = 0
S = [None] * n
S[0] = 1
size = 1
pos = 0
while pos < size:
	vert = S[pos]
	for k in tree[vert]:
		if val[vert] + k[1] <= val[k[0]]:
			val[k[0]] = max(0, val[vert] + k[1])
			S[size] = k[0]
			size += 1
	pos += 1
print(n - size)


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) = 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)
main()


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

class Graph(object):

	def __init__(self, n, d):
		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):
		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):
		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):
		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):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			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:
			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):
		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()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue
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(n - g.bfs3(0))


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)


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)


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)


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)


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():
	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 queue import deque
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)


from __future__ import print_function
from collections import *
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = [0] + gil()
adj = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	(p, w) = gil()
	adj[p].append((i, w))
st = [(1, 0, 0)]
ans = 0
while st:
	(p, sm, dmin) = st.pop()
	if p != 1 and sm - dmin > a[p]:
		continue
	ans += 1
	for (c, w) in adj[p]:
		st.append((c, sm + w, min(dmin, sm + w)))
print(n - ans)


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


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


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) = map(int, input().split())
	edge.get(p - 1, []).append((i + 1, c))
subtree_count()
print(remove_bfs())


from collections import deque
n = int(input())
val = [int(x) for x in input().split()]
dist = [0] * (n + 1)
g = [[] for i in range(n + 1)]
for i in range(2, n + 1):
	(a, b) = map(int, input().split())
	g[a].append((i, b))
r = 0
retira = [False] * (n + 1)
pilha = deque([1])
while pilha:
	v = pilha.pop()
	if retira[v]:
		r += 1
	for (u, d) in g[v]:
		dist[u] = max(d, dist[v] + d)
		if dist[u] > val[u - 1]:
			retira[u] = True
		else:
			retira[u] = retira[v]
		pilha.append(u)
print(r)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque

def dfs(x):
	stack = [x]
	while stack:
		x = stack.pop()
		for i in graph[x]:
			graph[i].remove(x)
			stack.append(i)

def dfs_simple(x):
	stack = [x]
	t = 0
	while stack:
		x = stack.pop()
		t += 1
		for i in graph[x]:
			stack.append(i)
	return t
n = int(input())
l = list(map(int, input().split()))
graph = {i: set() for i in range(n)}
d = {}
for i in range(1, n):
	(a, b) = map(int, input().split())
	a -= 1
	graph[a].add(i)
	graph[i].add(a)
	d[a, i] = b
dfs(0)
z = []
stack = [[0, 0]]
while stack:
	x = stack.pop()
	if x[1] > l[x[0]]:
		z.append(x[0])
	else:
		for i in graph[x[0]]:
			if (i, x[0]) in d:
				e = d[i, x[0]]
			else:
				e = d[x[0], i]
			if e >= 0:
				if x[1] >= 0:
					t = x[1] + e
				else:
					t = e
			elif x[1] >= 0:
				t = x[1] + e
			else:
				t = e
			stack.append([i, t])
count = 0
for i in z:
	count += dfs_simple(i)
print(count)


from collections import deque
n = int(input())
l = list(map(int, input().split()))
d = [0] * (n + 1)
x = [0]
for i in l:
	x.append(i)
m = [[] for i in range(n + 1)]
for i in range(2, n + 1):
	(a, b) = map(int, input().split())
	m[a].append((i, b))
s = 0
r = [False] * (n + 1)
p = deque([1])
while p:
	v = p.pop()
	if r[v]:
		s += 1
	for (i, j) in m[v]:
		d[i] = max(j, d[v] + j)
		if d[i] > x[i]:
			r[i] = True
		else:
			r[i] = r[v]
		p.append(i)
print(s)


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)


n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(n - 1):
	(p, c) = map(int, input().split())
	g[p - 1].append((i + 1, c))
cnt = 0
stack = [(0, 0)]
while stack:
	(node, dist) = stack.pop()
	if dist > a[node]:
		continue
	cnt += 1
	for (ver, dd) in g[node]:
		stack.append((ver, max(0, dist + dd)))
print(n - cnt)


from collections import deque
n = int(input())
val = [0] + list(map(int, input().split()))
maiordist = [0] * (n + 1)
g = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
	(a, b) = map(int, input().split())
	g[a].append((i, b))
pilha = deque([1])
while pilha:
	v = pilha.pop()
	for (u, d) in g[v]:
		maiordist[u] = max(d, maiordist[v] + d)
		pilha.append(u)
resp = 0
retira = [False] * (n + 1)
pilha = deque([1])
while pilha:
	v = pilha.pop()
	if retira[v]:
		resp += 1
	for (u, d) in g[v]:
		maiordist[u] = max(d, maiordist[v] + d)
		if maiordist[u] > val[u]:
			retira[u] = True
		else:
			retira[u] = retira[v]
		pilha.append(u)
print(resp)


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


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