CF208E Blood Cousins

题目描述

给定一片家族关系森林，共有 $n$ 个人，编号为 $1$ 到 $n$。每个人至多有一位父亲，父亲编号为 $0$ 表示没有父亲。家族关系不包含环。

若 $a$ 是 $b$ 的父亲，则称 $a$ 是 $b$ 的 $1$ 级祖先。对于 $p>1$，若 $b$ 存在父亲，且 $a$ 是 $b$ 的父亲的 $(p-1)$ 级祖先，则称 $a$ 是 $b$ 的 $p$ 级祖先。

如果两个人拥有同一个 $p$ 级祖先，则称他们互为 $p$ 级表亲。每次询问给出 $v,p$，请问编号为 $v$ 的人有多少个 $p$ 级表亲。注意，$v$ 本人不计入答案。如果 $v$ 不存在 $p$ 级祖先，则答案为 $0$。

输入格式

第一行一个整数 $n$，表示人数。

第二行 $n$ 个整数 $f_1,f_2,\ldots,f_n$，其中 $f_i$ 表示第 $i$ 个人的父亲编号，$f_i=0$ 表示没有父亲。

接下来一行一个整数 $m$，表示询问数。

接下来 $m$ 行，每行两个整数 $v,p$，表示一次询问。

输出格式

输出一行 $m$ 个整数，按询问顺序给出答案，整数之间用空格分隔。

样例

样例输入

5
0 1 1 2 2
4
4 1
4 2
2 1
1 1

样例输出

1 1 1 0

数据范围与约定

$1\le n,m\le 10^5$，$0\le f_i\le n$，$1\le v\le n$，$1\le p\le n$。