题目描述

题目名是吸引你点进来的。

给一棵边权为 $1$ 的树和一个常数 $X$，节点用 $1$ 到 $n$ 的整数表示。

定义 $dist(a,b)$ 为节点 $a,b$ 在树上的距离，即 $a$ 到 $b$ 的简单路径上的边权和，特别地，$dist(a,a) = 0$。

每次查询的时候给出一个区间 $[l,r]$，查询有多少个 $X$-块，定义如下：

对任意两个节点 $a,b$，定义 $a,b$ 是 $X$-连通的，当且仅当存在一个长为 $t$ 的节点序列 $\{v_i\}$，其中 $t$ 可以是任意正整数，满足：

1. $v_1=a$；
2. $v_t=b$；
3. 对任意 $1\le i\le t-1$，$dist(v_i,v_{i+1})\le X$；
4. 对任意 $1\le i\le t$，$l\le v_i\le r$。

定义“$X$-块”为一个点集 $S$，满足：

1. 对任意 $a$ 属于 $S$，$b$ 属于 $S$ 的补集且 $l\le b \le r$，$a,b$ 不是 X-连通的；
2. 对任意 $a,b$ 属于 $S$，$a$ 和 $b$ 是 X-连通的；
3. 对任意 $a$ 属于 $S$，有 $l\le a \le r$。

输入格式

第一行三个整数 $n$，$m$，$X$ 依次表示树的节点个数，询问次数，还有常数 $X$；

第二行共 $n-1$ 个整数 $p_2\;p_3\;\dots\;p_n$，表示对于 $2 \le i\le n$ 的整数 $i$，$i$ 和 $p_i$ 之间有一条无向边；

保证输入的数据构成一棵树；

之后 $m$ 行，每行两个整数 $l\;\;r$，表示这次询问的区间是 $[l,r]$，保证 $l \le r$；

保证 $1 \le n\le 3\cdot 10^5$，$1 \le m\le 6\cdot 10^5$。

输出格式

共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

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

提示

本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。

每个子任务的测试点满足一些特殊的限制，具体如下表：

其中，性质 1、性质 2 的含义如下：

性质 1：存在一个点 $w$ 使得 $dist(1,w)=n-1$；

性质 2：$n=m$，且第 $i$ 次询问为 $l=1,\;r=i$。