[Cnoi2019] 雪松果树

题目背景

幻想乡,冬。 一年一度,生长在高山上的雪松果树又结果了。 Cirno 不知从哪弄到了 $1,2,3\cdots9$ 颗雪松果,然后很开心的吃掉了其中 $6$ 颗,最后还剩最后 $1$ 颗。 Cirn o因为以后吃不到雪松果而感到忧愁,于是决定种在美丽的雾之湖畔。 第一天,发芽。 第二天,雪松果树长成了一颗参天大树, 上面长满了雪松果。 Cirno 在雪松果成熟之前早有一些问题想知道,但现在她忙于收集雪松果,就把问题丢给了你。

题目描述

雪松果树是一个以 $1$ 为根有着 $N$ 个节点的树。 除此之外, Cirno还有 $Q$ 个询问,每个询问是一个二元组 $(u,k)$ ,表示询问 $u$ 节点的 $k$-cousin 有多少个。 我们定义: > 节点 $u$ 的 $1$-father 为 路径 $(1, u)$ (不含 u)上距 u 最近的节点 > > 节点 $u$ 的 $k$-father 为 节点 「$u$ 的 $(k-1)$-father」 的 1-father > > 节点 $u$ 的 $k$-son 为所有 $k$-father 为 $u$ 的节点 > > 节点 $u$ 的 $k$-cousin 为 节点「 $u$ 的 $k$-father」的 $k$-son (不包含 $u$ 本身)

输入输出格式

输入格式


第一行,两个整数 $N$, $Q$ 第二行, $N-1$ 个整数,第 $i$ 个表示 $i+1$ 号节点的 1-father 以下 $Q$ 行,每行一个二元组$(u,k)$

输出格式


一行,$Q$ 个数,每一个表示一个询问的答案。若 u 不存在 k-father,输出 0。

输入输出样例

输入样例 #1

5 2
1 2 1 4
2 1
3 2

输出样例 #1

1 1

说明

数据范围: 对于0%-10%的数据 $N,Q \le 100$ 对于10%-20%的数据 $N \le 100,Q \le 10^6$ 对于 20%-30% 的数据 $N \le 10^5,Q \le100$ 对于 30%-35% 的数据 $N \le 10^4,Q \le 5000$ 对于 35%-50% 的数据 $N \le 10^5,Q \le 10^5$ 对于 50%-70% 的数据 保证树随机 对于 70%-100% 的数据 $N,Q \le 10^6$ 另外存在一组记 $20$ 分的 hack 数据。