题目描述

给定一棵有根树，包含 $n$ 个节点。节点编号为 $1 \dots n$，其中节点 1 是根节点。每个节点有一个值 $v_i$。

你希望将这棵树转化为一个堆。也就是说，你要选出尽可能多的节点，使得它们满足以下堆性质：对于选出的任意两个节点 $i$ 和 $j$，如果节点 $i$ 是节点 $j$ 在树上的祖先，则必须满足 $v_i > v_j$。注意，相等是不允许的。

请计算最多可以选出多少个节点组成这样的子集。该子集不一定要构成一棵子树。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示树中节点的数量。节点编号为 $1 \dots n$。

接下来的 $n$ 行，按顺序描述每个节点。每行包含两个整数 $v_i$ 和 $p_i$，其中 $v_i$（$0 \leq v_i \leq 10^9$）是节点的值，$p_i$（$0 \leq p_i < i$）是其父节点的编号。每个节点的编号都严格大于其父节点的编号。只有根节点 1 满足 $p_1 = 0$，因为它没有父节点。对于其他节点（$i = 2 \dots n$），有 $1 \leq p_i < i$。

输出格式

输出一个整数，表示满足堆性质的最大子集的节点数。

5
3 0
3 1
3 2
3 3
3 4

1

5
4 0
3 1
2 2
1 3
0 4

5

6
3 0
1 1
2 1
3 1
4 1
5 1

5

11
7 0
8 1
5 1
5 2
4 2
3 2
6 3
6 3
10 4
9 4
11 4

7

提示

翻译由 DeepSeek V3.2 完成