Counting Subtree Inclusion Sets

Given a rooted tree with \(n\) nodes. For any vertex \(w\) and any nonnegative integer \(d\), define \(N(w,d)\) as the set of nodes in the subtree rooted at \(w\) which have a distance at most \(d\) from \(w\). In other words, if the distance from \(w\) to a node \(x\) is at most \(d\), then \(x\) belongs to \(N(w,d)\).

You are given \(m\) queries. Each query provides a vertex \(w\) and a nonnegative integer \(d\). For each query, you are to calculate the size of the set \[ \{N(w',d') \mid N(w',d') \subseteq N(w,d)\}, \] that is, the number of distinct sets \(N(w',d')\) (over all possible vertices \(w'\) and nonnegative integers \(d'\)) which are contained in \(N(w,d)\). Note that if two different pairs \((w',d')\) yield the same set, they are counted only once.

Observation: For any vertex \(w'\) that lies in \(N(w,d)\), let the distance from \(w\) to \(w'\) be \(r\). Then \(N(w',d') \subseteq N(w,d)\) if and only if every node in \(N(w',d')\) (which is defined as the set of nodes in the subtree of \(w'\) within a distance \(d'\) from \(w'\)) satisfies \(r+d' \le d\). That is, the maximum valid \(d'\) is \(d-r\) (subject to the fact that increasing \(d'\) beyond the height of the subtree rooted at \(w'\) does not change \(N(w',d')\)).

Thus, if we denote by \(h(w')\) the height of the subtree rooted at \(w'\) (i.e. the maximum distance from \(w'\) to any descendant), then the distinct sets contributed by vertex \(w'\) (when \(w' \in N(w,d)\)) is
\[ \min\{h(w') , d - r\} + 1 \quad \text{with} \quad r = \text{dist}(w,w'). \]

The final answer for a query \((w,d)\) is the sum of \(\min\{h(w'), d - (\text{dist}(w,w'))\} + 1\) over all vertices \(w'\) in \(N(w,d)\).

inputFormat

The first line contains two integers, \(n\) and \(m\) (the number of nodes and the number of queries).

The second line contains \(n-1\) integers. The \(i\)-th integer (for \(i = 1, 2, \dots, n-1\)) indicates the parent of vertex \(i+1\) (thus, the tree is rooted at vertex 1).

Each of the next \(m\) lines contains two integers \(w\) and \(d\), representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of distinct sets \(N(w',d')\) that satisfy \(N(w',d') \subseteq N(w,d)\).

sample

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

8
3
1