Powerful Tree Triplets

Given a rooted tree $$\text{T}$$ with $$n$$ nodes numbered from 1 to $$n$$, where node 1 is the root, we define the following relations:

• For any two distinct nodes $$a$$ and $$b$$ in $$\text{T}$$, if $$a$$ is an ancestor of $$b$$ then we say that "$$a$$ is more powerful than $$b$$".
• For any two distinct nodes $$a$$ and $$b$$ in $$\text{T}$$, if the distance between $$a$$ and $$b$$ in the tree is at most a given constant $$x$$, then we say that "$$a$$ and $$b$$ are equally matched".

You are given a rooted tree $$\text{T}$$ with $$n$$ nodes and $$q$$ queries. Each query is specified by two integers $$p$$ and $$k$$. For each query, treat the node with number $$p$$ as fixed (denoted as $$a$$) and count the number of ordered triplets $$(a, b, c)$$ satisfying:

1. $$a$$, $$b$$, and $$c$$ are three distinct nodes in $$\text{T}$$, with $$a$$ fixed as the $$p$$th node.
2. Both $$a$$ and $$b$$ are ancestors of $$c$$ (i.e. they are more powerful than $$c$$).
3. $$a$$ and $$b$$ are equally matched; that is, the distance between them is at most $$k$$.

Note that since the tree is rooted, if both $$a$$ and $$b$$ are ancestors of $$c$$, then necessarily $$b$$ must lie in the subtree of $$a$$. In addition, because the unique path from the root to any node contains all its ancestors, once $$b$$ is chosen in the subtree of $$a$$ (with $$a$$ fixed), the valid nodes $$c$$ are exactly those in the subtree of $$b$$ (excluding $$b$$ itself).

Your task is to answer each query by computing the number of valid ordered triplets.

inputFormat

The first line contains two integers $$n$$ and $$q$$, representing the number of nodes in the tree and the number of queries, respectively.

The second line contains $$n-1$$ integers. The $$i$$th integer (for $$i = 1,2,\ldots,n-1$$) indicates the parent of node $$(i+1)$$.

Each of the following $$q$$ lines contains two integers $$p$$ and $$k$$, representing a query with the fixed node $$a = p$$ and the matching distance threshold $$k$$.

outputFormat

For each query, output a single integer — the number of ordered triplets $$(a, b, c)$$ satisfying the conditions.

sample

4 2
1 1 2
1 1
2 1

1
0