Problem Description

The title is just to attract you to click in.

You are given a tree whose edge weights are $1$, and a constant $X$. The nodes are labeled with integers from $1$ to $n$.

Define $dist(a,b)$ as the distance between nodes $a$ and $b$ on the tree, i.e. the sum of edge weights on the simple path from $a$ to $b$. In particular, $dist(a,a)=0$.

In each query, an interval $[l,r]$ is given. You need to ask how many $X$-blocks there are, defined as follows.

For any two nodes $a,b$, define that $a$ and $b$ are $X$-connected if and only if there exists a node sequence $\{v_i\}$ of length $t$, where $t$ can be any positive integer, such that:

1. $v_1=a$;
2. $v_t=b$;
3. For any $1 \le i \le t-1$, $dist(v_i,v_{i+1}) \le X$;
4. For any $1 \le i \le t$, $l \le v_i \le r$.

Define an "$X$-block" as a set of nodes $S$ satisfying:

1. For any $a \in S$ and any $b$ in the complement of $S$ with $l \le b \le r$, $a$ and $b$ are not $X$-connected;
2. For any $a,b \in S$, $a$ and $b$ are $X$-connected;
3. For any $a \in S$, $l \le a \le r$.

Input Format

The first line contains three integers $n$, $m$, $X$, denoting the number of nodes in the tree, the number of queries, and the constant $X$, respectively.

The second line contains $n-1$ integers $p_2\;p_3\;\dots\;p_n$, meaning that for each integer $i$ with $2 \le i \le n$, there is an undirected edge between $i$ and $p_i$.

It is guaranteed that the input forms a tree.

Then follow $m$ lines, each containing two integers $l\;\;r$, meaning the interval of this query is $[l,r]$. It is guaranteed that $l \le r$.

Constraints: $1 \le n \le 3 \cdot 10^5$, $1 \le m \le 6 \cdot 10^5$.

Output Format

Output $m$ lines, answering the queries in order. For each query, output one integer per line, which is the answer to this query.

10 9 2
1 1 1 2 3 4 1 1 1
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
5 5

1
1
2
3
3
3
2
1
1

Hint

This problem has multiple subtasks. Each subtask may contain multiple test points, and you can get the score of a subtask only if you pass all test points in that subtask.

The test points of each subtask satisfy some special constraints, as shown in the table below:

Here, the meanings of Property 1 and Property 2 are as follows.

Property 1: There exists a node $w$ such that $dist(1,w)=n-1$.

Property 2: $n=m$, and for the $i$-th query, $l=1,\;r=i$.

Translated by ChatGPT 5