← 返回题目列表

Codeforces · 682/C

C. 阿廖娜和树

中文机器翻译题面 查看原题

阿廖娜决定节食并去森林里拿一些苹果。在那里她意外地发现了一棵神奇的有根树,根在顶点1,每个顶点和每条边上都写着一个数字。

女孩注意到树的一些顶点是悲伤的,所以她决定玩它们。如果顶点 v 的子树中有一个顶点 u 且 dist(v, u) > au,则我们将顶点 v 称为悲伤的,其中 au 是写在顶点 u 上的数字,dist(v, u) 是写在从 v 到 u 的路径上的边上的数字之和。

树的叶子是通过单条边连​​接到单个顶点的顶点,但树的根当且仅当树由单个顶点(根)组成时才是叶子。

因此,Alyona 决定移除一些树叶,直到树上不再留下任何悲伤的顶点。 Alyona 需要去除的最少叶子数量是多少?

输入

在输入整数 n (1 ≤ n ≤ 105) 的第一行给出 — 树中的顶点数。

第二行给出了 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) 的序列,其中 ai 是写在顶点 i 上的数字。

接下来的 n - 1 行描述了树的边:第 i 行由两个整数 pi 和 ci 组成(1 ≤ pi ≤ n,- 109 ≤ ci ≤ 109),这意味着有一条边连接顶点 i + 1 和 pi,上面写有数字 ci。

输出

打印唯一的整数 - Alyona 需要移除的叶子的最小数量,这样树中就不会有任何悲伤的顶点。

示例

输入 #1

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

输出 #1

5

注意

下图表示从树上移除叶子的可能过程: