Problem Description

Given a tree whose edge weights are all $1$ and a constant $C$. The nodes are labeled by 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 $C$-blocks there are, defined as follows:

For any two nodes $a,b$, define that $a$ and $b$ are $C$-connected if and only if there exists a node sequence $\{v_i\}$ of length $t$ 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 C$.
4. For any $1\le i\le t$, $l\le v_i\le r$.

Define a "$C$-block" as a set of nodes $S$ such that:

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

Input Format

The first line contains three numbers $n$, $m$, $C$, representing the number of nodes in the tree, the number of queries, and the constant $C$, respectively.

The second line contains $n-1$ numbers $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 numbers $l\;\;r$, indicating that the interval of this query is $[l,r]$, and 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. Each line contains one integer, representing the answer to that 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

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

This problem has multiple subtasks. Each subtask may contain multiple test points. 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 restrictions, as shown in the table below:

The meanings of Additional Constraints 1 and Additional Constraints 2 are as follows:

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

Additional Constraints 2: $n=m$, and in the $i$-th query, $l=1,\;r=i$.

Translated by ChatGPT 5