家庭保险

题目描述

有一个由人 $1$、人 $2$、$\ldots$、人 $N$ 组成的家族。对于 $i \geq 2$,人 $i$ 的父母是人 $p_i$。

他们买了 $M$ 份保险。对于 $i=1,2,\ldots,M$,第 $i$ 份保险由人 $x_i$ 购买,该保险覆盖这个人以及其之后的 $y_i$ 代以内的子孙。

至少被一份保险覆盖的人有多少?

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$p_2$ $\ldots$ $p_N$
$x_1$ $y_1$
$\vdots$
$x_M$ $y_M$

输出格式

输出答案。

样例

7 3
1 2 1 3 3 3
1 1
1 2
4 3

4

第 $1$ 份保险覆盖人 $1$、$2$ 和 $4$,因为人 $1$ 的第 $1$ 代子孙是人 $2$ 和 $4$。

第 $2$ 份保险覆盖人 $1$、$2$、$3$ 和 $4$,因为人 $1$ 的第 $1$ 代子孙是人 $2$ 和 $4$,人 $1$ 的第 $2$ 代子孙是人 $3$。

第 $3$ 份保险覆盖人 $4$,因为人 $4$ 没有第 $1$、第 $2$ 或第 $3$ 代子孙。

因此,人 $1$、$2$、$3$、$4$ 共四个人至少被一份保险覆盖。

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

10

数据范围

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq M \leq 3 \times 10^5$
• $1 \leq p_i \leq i-1$
• $1 \leq x_i \leq N$
• $1 \leq y_i \leq 3 \times 10^5$
• 输入中的所有值均为整数。