Problem Description

Given a rooted tree with $n$ nodes, define $N(w,d)$ (where $w$ is a vertex of the tree and $d$ is a non-negative integer) as the set of nodes in the subtree rooted at $w$ whose distance to $w$ is at most $d$.

There are $m$ queries. Each query gives $w,d$ and asks for the size of $\{N(w',d')\mid N(w',d')\subseteq N(w,d)\}$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n-1$ integers $f_2,\dots,f_n$, where $f_i$ denotes the parent of node $i$.

The next $m$ lines each contain two integers $w,d$, representing one query.

Output Format

Output $m$ lines. Each line is the answer to the corresponding query in order.

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

3
1
1
7

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Constraints: For $100\%$ of the data, $1\le n,m\le 10^6$, $1\le f_i<i$, $1\le w\le n$, $0\le d\le n-1$.

For $25\%$ of the data, $n,m\le 100$.

For another $25\%$ of the data, $n,m\le 5000$.

For another $25\%$ of the data, $n,m\le 2\times 10^5$.

For the remaining $25\%$ of the data, there are no special restrictions.

Translated by ChatGPT 5