AT_abc309_e.[ABC309E] Family and Insurance

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

这个家系中的人一共加入了 $M$ 次保险。对于 $i=1,2,\ldots,M$ ，第 $i$ 次保险的投保人是人 $x_i$ ，被保险人包括本人以及其向下 $y_i$ 代以内的所有子孙。

请你求出，至少成为 $1$ 次保险的被保险人的人数。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$p_2$ $p_3$ $\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
```

输入#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

说明/提示

限制条件

$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$
输入均为整数

样例解释 1

对于第 $1$ 次保险，人 $1$ 的 $1$ 代以内的子孙是人 $2$ 和人 $4$ ，所以人 $1,2,4$ 是被保险人。
对于第 $2$ 次保险，人 $1$ 的 $1$ 代以内的子孙是人 $2$ 和人 $4$ ， $2$ 代以内的子孙是人 $3$ ，所以人 $1,2,3,4$ 是被保险人。
对于第 $3$ 次保险，人 $4$ 没有 $1,2,3$ 代以内的子孙，所以只有人 $4$ 是被保险人。
综上，至少成为 $1$ 次保险的被保险人的人数为人 $1,2,3,4$ 共 $4$ 人。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页