← 返回题目列表

AtCoder · abc309_e

H. 家庭和保险

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

分数: 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