分数: 425 点
问题陈述
有一个由人组成的家庭 1, 人 2, \ldots和人 N。 对于 i\geq 2, 人 i的父母是人 p_i.
他们买了保险 M 次。 对于 i=1,2,\ldots,M, 人 x_i 购买了 i-th 保险,涵盖该人及其后代 y_i 几代人。
有多少人拥有至少一项保险?
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M p_2 \ldots p_N x_1 y_1 \vdots x_M y_M
输出
打印答案。
示例输入 1
7 3 1 2 1 3 3 3 1 1 1 2 4 3
示例输出 1
4
的
树的 1-st 保险覆盖人群 1, 2,和 4,因为人 1的 1-st代子孙是人 2 和 4.
的
树的 2-nd 保险涵盖人员 1, 2, 3,和 4,因为人 1的 1-st代子孙是人 2 和 4和人 1的 2-nd代后代是人 3.
的
树的 3-rd 保险涵盖人员 4,因为人 4 没有 1-st, 2-nd,或 3-rd 后代。
所以,四个人,人 1, 2, 3,和 4,至少有一份保险承保。
示例输入 2
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
示例输出 2
10