ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 C: 阿洛纳和树

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：3 通过：3
返回比赛提交提交记录

题目描述

Alyona决定节食，然后去森林里买一些苹果。在那里，她意外地发现了一棵神奇的根树，它的根位于顶点1，每个顶点和每条边上都写着一个数字。
女孩注意到树的一些顶点是悲伤的，所以她决定玩它们。让我们称顶点v为sad，如果顶点v的子树中有一个顶点u，使得dist（v，u）>au，其中au是写在顶点u上的数字，dist（v，u）是写在从v到u的路径上的边上的数字的和。
树的叶子是通过单个边连接到单个顶点的顶点，但树的根是叶子，当且仅当树由单个顶点-根组成。
因此，Alyona决定移除一些树叶，直到树上没有任何悲伤的顶点。Alyona需要移除的最小树叶数量是多少？

输入格式

在输入整数n（1≤n≤105）的第一行中，给出了树中顶点的数量。

在第二行中，。。。，给出（1≤ai≤109），其中ai是写在顶点i上的数字。

接下来的n-1行描述了树边：其中第i行由两个整数pi和ci（1≤pi≤n，-109≤ci≤109）组成，这意味着有一条边连接顶点i+1和pi，上面写有编号ci。

输出格式

打印唯一的整数–Alyona需要删除的最小叶子数，这样树中就不会留下任何悲伤的顶点。
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

输入样例 复制 

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

输出样例 复制 

5

数据范围与提示

下图显示了从树上移除树叶的可能过程：

分类标签