Family and Insurance

题目描述

有一个家庭，由第 $1$ 个人、第 $2$ 个人、… 和第 $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

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$ 所有输入值均为整数。第 $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$，至少被一份保险覆盖。

标签: AtCoder|abc309E

来源

AtCoder|abc309E